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:
- $P$ is wholly contained within the interior of the convex hull of $S$:
$P subsetneq text{convexhull}(S)$.
- $O$ is contained within the interior of $P$, namely: $O in P$.
- 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$ 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!!!