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

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 = "Funding Information: Acknowledgements Research by Akitaya, Aloupis, and T{\'o}th 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. Publisher Copyright: {\textcopyright} 2017, Springer Science+Business Media, LLC.",

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

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 - Funding Information: Acknowledgements Research by Akitaya, Aloupis, and Tóth 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. Publisher Copyright: © 2017, Springer Science+Business Media, LLC.

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 - http://www.scopus.com/inward/record.url?scp=85010708607&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010708607&partnerID=8YFLogxK

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