I actually don't know, whether the polygon I describe here already has name, but let me explain the problem, that is solved by the polygon, with a little story:
Imagine a flat terrain with bushes of bamboo (depicted by the red dots), a monk, that has chosen two of those bushes as the endpoints of his meditation path (depicted by the fat orange line), and further a tiger that is curious about what is going on.
What the tiger wants to do is to encircle the monk, running from bush to bush to become invisible there and of course the tiger wants to have free sight on the entire meditation-path from every bush in front of which it lays down. To that end, the tiger may either include any of the bushes of the meditation path or not. The problem instance - clarification in response to Joseph O'Rourke's answer
The polygon with the vertices of the meditation path included
The polygon with the vertices of the meditation path excluded
The solution of the above stated problem is the polygon formed by the corners of a maximal set of empty triangles with the "meditation path" as their common side $c$.
If the endpoints of the meditation path are $A$ and $B$, with associated coordinates $(0,0)$ and $(1,0)$, then the set $\lbrace C_i\rbrace$ of third corners of the maximal set of empty triangles with common side $c$ is sorted according to the angle of sides $b_i:=C_i-A$ with side $c:=B-A$ (or according to the angles of the sides $a_i$ with $c$)
So this question is neither about what the solution to the tiger's problem is, nor about how to calculate the polygon.
Questions:
is there already a name for the either of the variants of the "curious tiger" polygon?
which (if any) generalizations of the 2D problem to higher, $d$-dimensional euclidean spaces, have as a solution a maximal set of points from which an unobstructed view to the entire lower-dimensional "meditation-simplex" is possible and.
such that that maximal set of points defines the corners of a $d$-dimensional polytope, that is topologically equivalent to the $(d-1)$-sphere and
that every point of that polytope has an unobstructed view onto the entire "meditation-simplex"?
The reason why I am interested in those kind of polygons, resp. polytopes, is that they would allow for new algorithms for two wellknown problems in computational geometry: Shape Hulls and Tour Expansion Heuristics for the planar euclidean TSP can be improved by looking for large "Curious Tiger" Polygons (CTPs).
If no holes are allowed, then the following heuristic can be applied to both problems:
- take the edges of the convex hull as the meditation paths
- perform a greedy relaxation on the points that are contained in multiple CTPs until no pair of those polygons has an edge in common.
If holes are allowed, also inner edges may serve as meditation paths:
- repeat the above steps as long as considered necessary
In the extreme every edge would generate an initial CTP and the relaxing would be performed while guaranteeing that topological constraints are not violated.
A challenging instance of finding a shapehull; starting with the convex hull, the CTP over one of the edges (depicted in orange) yields a convincing solution.
Illustrative example demonstrating how the CTP is superior to distance based shapehull algorithms.