Recognizing Weakly Simple Polygons

Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, Csaba D. Tóth

Research output: Contribution to journalArticlepeer-review

Abstract

We present an O(nlog n) -time algorithm that determines whether a given n-gon in the plane is weakly simple. This improves upon an O(n2log n) -time algorithm by Chang et al. (Proceedings of the 26th ACM-SIAM symposium on discrete algorithm, SIAM, 2015). Weakly simple polygons are required as input for several geometric algorithms. As such, recognizing simple or weakly simple polygons is a fundamental problem.

Original languageEnglish (US)
Pages (from-to)785-821
Number of pages37
JournalDiscrete and Computational Geometry
Volume58
Issue number4
DOIs
StatePublished - Dec 1 2017

Keywords

  • Combinatorial embedding
  • Perturbation
  • Simple polygon

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Recognizing Weakly Simple Polygons'. Together they form a unique fingerprint.

Cite this