Recognizing Weakly Simple Polygons

Emerging

0
Citations
0
Refs
2016
Year
Search Works
Work Details
  • DOI 10.4230/lipics.socg.2016.8
  • OpenAlex ID W2762324796
  • Type Preprint
  • Language EN
  • Published 01 Jan 2016
  • Source arXiv (Cornell University)
  • Publisher Cornell University
  • Countries 2
  • Institutions 4
  • Added 10 Oct 2025
  • Updated 14 Oct 2026
External Links
OpenAlex Record DOI Resolver PDF Publisher Page
MENU
0

Recognizing Weakly Simple Polygons

Preprint 2016 EN Green

We present an O(n log n)-time algorithm that determines whether a given planar n-gon is weakly simple. This improves upon an O(n^2 log n)-time algorithm by [Chang, Erickson, and Xu, SODA, 2015]. Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.

0

Citations

0

References

4

Authors

0.00

FWCI

Topics
Keywords
Authors & Affiliations
4 authors
#AuthorInstitutionsORCID
1 Hugo A. Akitaya Tufts University (US)
2 Greg Aloupis A Tufts University (US) —
3 Jeff Erickson National Center for Supercompu… (BG) National Center for Supercompu… (US)
4 Csaba D. Tóth California State University, N… (US)
Related Works
20

Data: OpenAlex