Monotone polygon: Difference between revisions
monotone polygonal chain |
No edit summary |
||
| Line 4: | Line 4: | ||
Similarly, a [[polygonal chain]] ''C'' is called '''monotone''' with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects ''C'' at most once. |
Similarly, a [[polygonal chain]] ''C'' is called '''monotone''' with respect to a straight line ''L'', if every line orthogonal to ''L'' intersects ''C'' at most once. |
||
For many practical purposes this definition may be extended to allow cases when some edges of ''P'' are orthogonal to ''L'', and a polygon may be called monotone, if a line segment that connects two points in ''P'' and is orthogonal to ''L'' completely belongs to ''P''. |
For many practical purposes this definition may be extended to allow cases when some edges of ''P'' are orthogonal to ''L'', and a [[simple polygon]] may be called monotone, if a line segment that connects two points in ''P'' and is orthogonal to ''L'' completely belongs to ''P''. |
||
Following the terminology for [[monotone function]]s, the former definition described '''polygons strictly monotone''' with respect to ''L''. The "with respect to" part is necessary for drawing the strict/nonstrict distinction: a polygon nonstrictly monotone with respect to ''L'' is strictly monotone with respect to a line ''L<sub>1</sub>'' rotated from ''L'' by a sufficiently small angle. |
Following the terminology for [[monotone function]]s, the former definition described '''polygons strictly monotone''' with respect to ''L''. The "with respect to" part is necessary for drawing the strict/nonstrict distinction: a polygon nonstrictly monotone with respect to ''L'' is strictly monotone with respect to a line ''L<sub>1</sub>'' rotated from ''L'' by a sufficiently small angle. |
||
Revision as of 18:59, 19 April 2010
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]
Similarly, a polygonal chain C is called monotone with respect to a straight line L, if every line orthogonal to L intersects C at most once.
For many practical purposes this definition may be extended to allow cases when some edges of P are orthogonal to L, and a simple polygon may be called monotone, if a line segment that connects two points in P and is orthogonal to L completely belongs to P.
Following the terminology for monotone functions, the former definition described polygons strictly monotone with respect to L. The "with respect to" part is necessary for drawing the strict/nonstrict distinction: a polygon nonstrictly monotone with respect to L is strictly monotone with respect to a line L1 rotated from L by a sufficiently small angle.
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]
See also
- Orthogonal convexity, for polygons which are monotone simultaneously with respect to two mutually orthogonal directions; also a generalization for any number of fixed directions.
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:10.1145/357337.357341, 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.