3
$\begingroup$

Dear mathoverflow community,

working on a visualization project I encountered a geometric problem, which I have not yet heard about and am interested in solving algorithmically. However a mere hint of what the problem might be called and what literature might deal with it would be very helpful as well:

In geometry a polygon P in the plane may be called monotone with respect to a line L, if every line orthogonal to L intersects P at most twice. I am however interested in the question, whether a polygon P is "monotone with respect to a point p", which I chose to mean that every straight line containing p intersects P at most twice.

Two Polygons being "monotone" (left) and not "monotone" (right) to a point

To test this property I created a line from p through every vertex of P and counted the intersections with P. If none of those lines had more than two intersection points with P, I accepted P to be "monotone to p".

This property is easily extendible to 3D polyhedra: Every line through p shall intersect the polyhedron at most twice.

There are three main questions I am going to ask you about all this:

  1. Does a name for this problem/property already exist? Which literature may deal with the property and recognition of polygon/polyhedra with this property.

  2. In 3D, is it still sufficient to test every vertex to recognize a polyhedron with this property? (creating a line through p and every vertex each and counting the intersection points for the line with the polyhedron)
    Answered

    2.1 If the polyhedron was limited to contain only axis aligned edges, would the per-vertex recognition suffice?

  3. If an alternative algorithm comes to mind (especially if the answer to 2 turns out to be no) I am very glad to gather some ideas for algorithms for recognition of polyhedra with this property.

Possible Algorithms :

  1. Extend the polygon/polyhedron to contain p. Check if p is inside kernel.
  2. Apply projective transformation to polygon/polyhedron reducing problem to monotony with respect to a line.

Thanks in advance.

Kind regards,

Kilian Werner

$\endgroup$
  • $\begingroup$ Perhaps reasonable terms are point-monotone or externally star-shaped. $\endgroup$ – Joseph O'Rourke Sep 21 '16 at 14:15
  • $\begingroup$ Extending the polygon to contain $p$ and then checking to see if $p$ is in the kernel will not always work, because the portion removed as part of the extending could contain convolutions that cross a ray from $p$ several times. $\endgroup$ – Joseph O'Rourke Sep 22 '16 at 11:44
  • $\begingroup$ @JosephO'Rourke Is this true? Even if the extension removes only faces that are entirely visible from p? $\endgroup$ – K. Werner Sep 22 '16 at 12:20
  • $\begingroup$ I was assuming a particular meaning to "extending the polygon to contain $p$," I guess not your meaning. I don't see how to extend the polygon by only removing edges entirely visible from $p$. Because what's behind those edges could be arbitrarily convoluted. $\endgroup$ – Joseph O'Rourke Sep 22 '16 at 19:07
4
$\begingroup$

If the point $p$ is inside $P$, then "monotone with respect to a point" is called "star-shaped". If the point is outside, then I don't know of any special name.

An observation: if $p$ is outside, then a projective transformation sends a polygon/polyhedron monotone with respect to $p$ to one monotone with respect to a line. One has to send to infinity a line through $p$ that does not intersect $P$. That such a line exists follows from the monotonicity.

The answer to 2 is "no". A counterexample is provided by the Schoenhardt polyhedron. (Take $p$ above the top face.)

$\endgroup$
  • $\begingroup$ Thanks for your quick reply. "Star-shaped" is indeed very similar to my property. In fact one could remove all faces in P entirely visible from p and close the polygon/polyhedron by constructing new faces to p. Now computing the kernel of the constructed polygon/polyhedron and checking whether p is part of it would solve the problem. The projection you mentioned would reduce the problem to (common) monotony, however I am not aware of a 3D extension of this problem. Thank you for answering question 2. However I could limit the problem to a special scenario to circumvent that. (see above) $\endgroup$ – K. Werner Sep 22 '16 at 9:07

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.