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
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]
A monotone polygon may be easily triangulated in linear time.[2]
A polygon monotone with respect to a horizontal line that has the minimum perimeter among all monotone polygons with a given set of vertices, is called a minimum bitonic tour. It may be found in polynomial time using dynamic programming.[3]
[edit] References
- ^ 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.
- ^ Fournier, A.; Montuno, D. Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics 3 (2): 153–174, doi:, ISSN 0730-0301
- ^ Introduction to Algorithms, 2nd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2001. Problem 15-1, p. 364.
