Defining a convex "hole"

60 Views Asked by At

How could we define the idea of the inverse of the convex hull? To clarify, not what is the innermost convex hull without recursively drawing and removing convex hulls, but maximizing a convex shape such that it only includes itself and some given center.

My draft definition is:

Given a finite set of points $S \subset {\Bbb R}^2$ and an arbitrary point contained within $S$ C, the convex hole of $C$ is the largest convex shape whose vertices are contained within $S$, and contains only itself and point $C$. There are two problems that I have found in this definition: should the vertices of the convex hole contain $C$, and what is "largest"?

If the convex hole's vertices don't contain $C$, then I believe this gives a more concrete singular solution, as you expand outwards from point $C$, creating the largest shape you can. If you do include $C$, then you have numerous possible shapes that can arise with $C$ as a vertex and then must find the largest one, which is where the second problem really arises. Example with left: excluding $C$ from the vertices and right: including $C$ with the vertices. Sides that intersect another area are dotted

With some discussion in person, there are two definitions of "largest": in terms of the area of the resulting polygon or in terms of the number of points. This only arises in the second case of including $C$ in the vertices because you can create two different shapes that could each be "larger" than the other due to the spread of the points. Example with left: a convex hole with a larger area and $5$ vertices and right: a convex hole with a smaller area and $8$ vertices

To restate the questions: should the convex hole's vertices contain the given center $C$, and by what quality should "large" be defined? I am not a mathematician, so if there are details in more formal definitions of a convex hull that would provide clarity on the issues, please explain them.