# #StackBounty: #algorithms #optimization #linear-programming #convex-hull How to find the supremum of all the "good" (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):

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\$ 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!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.