1 Search Results for "Aloupis, Greg"


Document
Recognizing Weakly Simple Polygons

Authors: Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba Tóth

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)


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

Cite as

Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba Tóth. Recognizing Weakly Simple Polygons. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{akitaya_et_al:LIPIcs.SoCG.2016.8,
  author =	{Akitaya, Hugo A. and Aloupis, Greg and Erickson, Jeff and T\'{o}th, Csaba},
  title =	{{Recognizing Weakly Simple Polygons}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.8},
  URN =		{urn:nbn:de:0030-drops-59003},
  doi =		{10.4230/LIPIcs.SoCG.2016.8},
  annote =	{Keywords: weakly simple polygon, crossing}
}
  • Refine by Author
  • 1 Akitaya, Hugo A.
  • 1 Aloupis, Greg
  • 1 Erickson, Jeff
  • 1 Tóth, Csaba

  • Refine by Classification

  • Refine by Keyword
  • 1 crossing
  • 1 weakly simple polygon

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail