Weakly simple polygon

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

In geometry, a weakly simple polygon is a generalization of a simple polygon, allowing the polygon sides to touch each other in limited ways. Different authors have defined weakly simple polygons in different ways:

One definition is that, when a simply connected open set in the plane is bounded by finitely many line segments, then its boundary forms a weakly simple polygon.^[1] In the image, ABCDEFGHJKLM is a weakly simple polygon according to this definition, with the color blue marking the region for which it is the boundary. This type of weakly simple polygon can arise in computer graphics and CAD as a computer representation of polygonal regions with holes: for each hole a "cut" is created to connect it to an external boundary. Referring to the image above, ABCM is an external boundary of a planar region with a hole FGHJ. The cut ED connects the hole with the exterior and is traversed twice in the resulting weakly simple polygonal representation.

In an alternative and more general definition of weakly simple polygons, they are the limits of sequences of simple polygons. The polygons in the sequence should all have the same combinatorial type as each other, with convergence under the Fréchet distance.^[2] This formalizes the notion that such a polygon allows segments to touch but not to cross. This generalizes the notion of the polygonal boundary of a topological disk: this boundary is the limit of a sequence of polygons, offset from it within the disk. However, this type of weakly simple polygon does not need to form the boundary of a region, as its "interior" can be empty. For example, referring to the same image, the polygonal chain ABCBA is a weakly simple polygon according to this definition: it may be viewed as the limit of "squeezing" of the polygon ABCFGHA.

References

^ Dumitrescu, Adrian; Tóth, Csaba D. (2007). "Light orthogonal networks with constant geometric dilation". In Thomas, Wolfgang; Weil, Pascal (eds.). STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings (illustrated ed.). Springer. p. 177. ISBN 978-3540709176.
^ Chang, Hsien-Chih; Erickson, Jeff; Xu, Chao (2015). "Detecting weakly simple polygons". In Indyk, Piotr (ed.). Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015. {SIAM}. pp. 1655–1670. arXiv:1407.3340. doi:10.1137/1.9781611973730.110.

[1] Dumitrescu, Adrian; Tóth, Csaba D. (2007). "Light orthogonal networks with constant geometric dilation". In Thomas, Wolfgang; Weil, Pascal (eds.). STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings (illustrated ed.). Springer. p. 177. ISBN 978-3540709176.

[2] Chang, Hsien-Chih; Erickson, Jeff; Xu, Chao (2015). "Detecting weakly simple polygons". In Indyk, Piotr (ed.). Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015. {SIAM}. pp. 1655–1670. arXiv:1407.3340. doi:10.1137/1.9781611973730.110.

[1]

[2]