Out of a set of vertices $V=\{\vec v_i\in \mathbb R^D\}$, I am constructing a piecewise linear interpolating function $f:\mathbf{conv}(V)\rightarrow R$ as follows: given a point $\vec d\in \mathbf{conv}(V)$, I want to construct the smallest convex hull out of given vertices:

  1. a convex hull $H = \mathbf{conv}(P=\{\vec p_i\})$
  2. from the given vertices $P=\{\vec p_i\}\subseteq\{\vec v_i\}$,
  3. that contains the given point $\vec d\in H$,
  4. that does not contain any other given vertices as interior points $\forall \vec v_i, \vec v_i \notin P <=> \vec v_i\notin H$. All points belonging to a face or edge should be included into $P$.
  5. It does not have to be of the full dimension $H\subset\mathbb R^d, d \leq D$.

This way, I can guarantee that the interpolation will not "extrapolate" (e.g. yield values $f>\max f(\vec v_i)$ or $f<\min f(\vec v_i)$).

Question: how do I construct such a set in the simplest way? I don't need the computationally optimal, just a reasonable solution. E.g. defining and checking all the possible polytopes seems slow and bug-prone.

Difference from the "classical" convex hull search - It can be defined

  • minimal - contains as few of $V$ vertices as possible $\forall \vec p_j\in P,\vec d\notin \mathbf{conv}(P\setminus\{\vec p_j\})$
  • maximal - contains as many $V$ vertices as possible, but only as $P$ elements, not interior points

Hopefully, the latter is enough to make the solution unique. Otherwise, any solution will do.

Ideas on solution: It should be useful to sort the vertices by distance from $p$ and take one by one, until the is.complete(polytope), such as in incremental hull construction. Then we may need pruning.

We may need less or more than $D+1$ vertices. As for the criteria, I tried to make sure that for each dimension, there is either 1 vertex with the same coordinate (it will happen in my setup), or 2 vertices with coordinates greater and less than the given. However, for $D=2$, you can try to draw a triangle and see that this is maybe a necessary, but not sufficient criteria.

Another idea is to try projecting $\vec d$ on all possible faces. The projection will fall within all faces of the proper hull.

Disclaimer: a software that does this would also do, but I coudn't find any that seemed to do this.

  • $\begingroup$ Let me try to understand. You're given a set of vertices $\{v_i\} \subset \Bbb R^D$, as well as a point, $p \in \Bbb R^D$. Presumably, $p$ is inside the convex hull of $\{v_i\}$ (a polytope), which I would write as $p \in \operatorname{conv}(\{v_i\})$. Your question, then, is: How can I find $S \subseteq \{v_i\}$ with minimal cardinality, such that $p$ is still in the convex hull $\rm{conv}(S)$? $\endgroup$ – pjs36 Mar 26 '15 at 20:35
  • $\begingroup$ You might want to at least add something along those lines to your question; some parts don't make a lot of sense, like saying a polytope $P$ is a subset of a set of discrete vertices $\{v\}$; that's why I wanted to make sure I understood. As far as the existence of $S$: If $p$ really is in the convex hull of $\{v_i\}$, then such a set $S \subseteq \{v_i\}$ is guaranteed to exist, it just might not be a proper subset of the vertices, or be unique (but its size is). Is $p$ guaranteed to be in the convex hull, in your setup? $\endgroup$ – pjs36 Mar 26 '15 at 22:58
  • $\begingroup$ I relaxed the definition of the proper hull, added the existence condition you mentioned, and removed any requirement of uniqueness. $\endgroup$ – Leo Mar 27 '15 at 23:01
  • $\begingroup$ I've been thinking about the problem a bit more. I will hopefully be able to write something up in a little while (a few hours to a day or so). $\endgroup$ – pjs36 Mar 27 '15 at 23:40
  • $\begingroup$ Have you checked whether Delaunay triangulation might help you? If so, CGAL would do the job for you (doc.cgal.org/latest/Manual/…) $\endgroup$ – Willem Hagemann Apr 15 '15 at 14:05

According to the comments above, the questioner was quite happy with my proposal to use CGAL to solve his problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.