5
$\begingroup$

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. Curious-Tiger Polygon - the Problem Instance The problem instance - clarification in response to Joseph O'Rourke's answer


Curious-Tiger Polygon with vertices of meditation path included The polygon with the vertices of the meditation path included


Curious-Tiger Polygon with vertices of meditation path excluded 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.

Curious-Tiger Polygon - Shapehull Instance 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.

Curious Tiger Polygon - Shapehull Example
Illustrative example demonstrating how the CTP is superior to distance based shapehull algorithms.

$\endgroup$
1
$\begingroup$

Weak-visibility polygons are something like the reverse viewpoint of what you are exploring:

"A polygon is said to be a weak visibility polygon if every point of the polygon is visible from some point of an internal segment."

Ghosh, Subir Kumar, Anil Maheshwari, Sudebkumar Prasant Pal, Sanjeev Saluja, and CE Veni Madhavan. "Characterizing and recognizing weak visibility polygons." Computational Geometry 3, no. 4 (1993): 213-233. (Journal link.)


         


In your setup, the "meditation path" is the internal segment. There is a difference in that you want "free sight on the entire meditation-path," whereas "weak visibility" only requires visibility from "some point of [the] internal segment." Naturally, changing "some point" to "all points" changes "weak visibility" to "strong visibility." This distinction was introduced by Avis & Toussaint, and is described in my book Art Gallery Theorems and Algorithms, Chap.8. So I would suggest strong-visibility polygons as a key search term.

I'm not finding the ideal paper on strong visibility, but this might be a start:

Akbari, Hoda, and Mohammad Ghodsi. "Visibility maintenance of a moving segment observer inside polygons with holes." In Candadian Conf. Comput. Geom., pp. 117-120. 2010. (CCCG Proceedings link.)

$\endgroup$
  • $\begingroup$ Thanks for your answer Joseph, but you have misinterpreted my question (my fault because I haven't made it explicit enough in my question): the initial situation is only a set of discrete points, in the plane and a single line segment that resembles the meditation path. The task is then to determine the set of points from which the linesegment can be seen completely. I will edit my question to make that more obvious. $\endgroup$ – Manfred Weis Dec 9 '18 at 5:11
  • $\begingroup$ Another difference to Art Gallery problems is that CTPs can be constructed in $O(n \log n)$ while the weak visibility of from an edge takes $O(n^2)$ according to the cited article. $\endgroup$ – Manfred Weis Dec 9 '18 at 6:10
  • $\begingroup$ @ManfredWeis: Yes, I understood your question. I was just responding to "is there already a name...?" I don't think there is a name, but the polygon you describe is strongly visible from the internal segment. So it's more a connection to the visibility literature. $\endgroup$ – Joseph O'Rourke Dec 9 '18 at 23:48
  • $\begingroup$ thanks for that clarification. The vertices of the CTP are however also a superset of the corners that a walking guard can see in a closed polygonal room; so may determining the vertices of the CTP first and then filtering out the invisible ones, might speed up practical implementations of the calculation of the weak visibility polygon. I see however the major benefit of the CTP in the Shapehull and TSP-heurisitcs area. $\endgroup$ – Manfred Weis Dec 10 '18 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.