Recognizing Weakly Simple Polygons

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

doi:10.1007/s00454-017-9918-3

Recognizing Weakly Simple Polygons

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

Siebel School of Computing and Data Science

Research output: Contribution to journal › Article › peer-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(n²log 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 language	English (US)
Pages (from-to)	785-821
Number of pages	37
Journal	Discrete and Computational Geometry
Volume	58
Issue number	4
DOIs	https://doi.org/10.1007/s00454-017-9918-3
State	Published - 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

Online availability

10.1007/s00454-017-9918-3

Library availability

Discover UIUC Full Text

Cite this

@article{c0e1fdf8563e42f3895e66f0b8c0e93d,

title = "Recognizing Weakly Simple Polygons",

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.",

keywords = "Combinatorial embedding, Perturbation, Simple polygon",

author = "Akitaya, \{Hugo A.\} and Greg Aloupis and Jeff Erickson and T{\'o}th, \{Csaba D.\}",

note = "Acknowledgements Research by Akitaya, Aloupis, and T\textbackslash{}u00F3th was supported in part by the NSF awards CCF-1422311 and CCF-1423615. Akitaya was supported by the Science Without Borders program. Research by Erickson was supported in part by the NSF award CCF-1408763. We thank Anika Rounds and Diane Souvaine for many helpful conversations that contributed to the completion of this project. We thank the anonymous referees for many useful comments and suggestions.",

year = "2017",

month = dec,

day = "1",

doi = "10.1007/s00454-017-9918-3",

language = "English (US)",

volume = "58",

pages = "785--821",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Recognizing Weakly Simple Polygons

AU - Akitaya, Hugo A.

AU - Aloupis, Greg

AU - Erickson, Jeff

AU - Tóth, Csaba D.

N1 - Acknowledgements Research by Akitaya, Aloupis, and T\u00F3th was supported in part by the NSF awards CCF-1422311 and CCF-1423615. Akitaya was supported by the Science Without Borders program. Research by Erickson was supported in part by the NSF award CCF-1408763. We thank Anika Rounds and Diane Souvaine for many helpful conversations that contributed to the completion of this project. We thank the anonymous referees for many useful comments and suggestions.

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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.

AB - 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.

KW - Combinatorial embedding

KW - Perturbation

KW - Simple polygon

UR - https://www.scopus.com/pages/publications/85010708607

UR - https://www.scopus.com/pages/publications/85010708607#tab=citedBy

U2 - 10.1007/s00454-017-9918-3

DO - 10.1007/s00454-017-9918-3

M3 - Article

AN - SCOPUS:85010708607

SN - 0179-5376

VL - 58

SP - 785

EP - 821

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

Recognizing Weakly Simple Polygons

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this