Monotone polygon

From Wikipedia, the free encyclopedia

In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice.[1]

For many practical purposes this definition may be extended to allow cases when some edges of P are orthogonal to L.

[edit] Properties

Green indicates one intersection, blue indicates two intersections, and red indicates three or more. The top two polygons are monotone while the bottom two are not.
Green indicates one intersection, blue indicates two intersections, and red indicates three or more. The top two polygons are monotone while the bottom two are not.

Assume that L coincides with the x-axis. Then the leftmost and rightmost vertices of a monotone polygon decompose its boundary into two monotone polygonal chains such that when the vertices of any chain are being traversed in their natural order, their X-coordinates are monotonically increasing or decreasing. In fact, this property may be taken for the definition of monotone polygon and it gives the polygon its name.

A convex polygon is monotone with respect to any straight line.

Point in polygon queries with respect to a monotone polygon may be answered in logarithmic time after linear time preprocessing (to find the leftmost and rightmost vertices).[1]

[edit] References

  1. ^ a b Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.