#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supremum of polytopes which are interior …

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

  1. $P$ is wholly contained within the interior of the convex hull of $S$:
    $P subsetneq text{convexhull}(S)$.

  2. $O$ is contained within the interior of $P$, namely: $O in P$.

  3. none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.


Here is a 2D modest illustration (the green polytope might not be really the optimal):

example

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $alpha$-shapes or $beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT


EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.


Get this bounty!!!

Leave a Reply