On k-convex polygons
Original manuscript" July 21, 2010
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86056 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826217095669481472 |
|---|---|
| author | Aichholzer, Oswin Aurenhammer, Franz Demaine, Erik D. Hurtado, Ferran Ramos, Pedro Urrutia, Jorge |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Aichholzer, Oswin Aurenhammer, Franz Demaine, Erik D. Hurtado, Ferran Ramos, Pedro Urrutia, Jorge |
| author_sort | Aichholzer, Oswin |
| collection | MIT |
| description | Original manuscript" July 21, 2010 |
| first_indexed | 2024-09-23T16:57:56Z |
| format | Article |
| id | mit-1721.1/86056 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:57:56Z |
| publishDate | 2014 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/860562022-09-29T22:42:49Z On k-convex polygons Aichholzer, Oswin Aurenhammer, Franz Demaine, Erik D. Hurtado, Ferran Ramos, Pedro Urrutia, Jorge Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Original manuscript" July 21, 2010 We introduce a notion of k -convexity and explore polygons in the plane that have this property. Polygons which are k -convex can be triangulated with fast yet simple algorithms. However, recognizing them in general is a 3SUM-hard problem. We give a characterization of 2-convex polygons, a particularly interesting class, and show how to recognize them in O(n logn) time. A description of their shape is given as well, which leads to Erdős–Szekeres type results regarding subconfigurations of their vertex sets. Finally, we introduce the concept of generalized geometric permutations, and show that their number can be exponential in the number of 2-convex objects considered. 2014-04-07T16:49:37Z 2014-04-07T16:49:37Z 2011-09 2010-12 Article http://purl.org/eprint/type/JournalArticle 09257721 http://hdl.handle.net/1721.1/86056 Aichholzer, Oswin, Franz Aurenhammer, Erik D. Demaine, Ferran Hurtado, Pedro Ramos, and Jorge Urrutia. “On k-Convex Polygons.” Computational Geometry 45, no. 3 (April 2012): 73–87. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1016/j.comgeo.2011.09.001 Computational Geometry Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Elsevier arXiv |
| spellingShingle | Aichholzer, Oswin Aurenhammer, Franz Demaine, Erik D. Hurtado, Ferran Ramos, Pedro Urrutia, Jorge On k-convex polygons |
| title | On k-convex polygons |
| title_full | On k-convex polygons |
| title_fullStr | On k-convex polygons |
| title_full_unstemmed | On k-convex polygons |
| title_short | On k-convex polygons |
| title_sort | on k convex polygons |
| url | http://hdl.handle.net/1721.1/86056 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT aichholzeroswin onkconvexpolygons AT aurenhammerfranz onkconvexpolygons AT demaineerikd onkconvexpolygons AT hurtadoferran onkconvexpolygons AT ramospedro onkconvexpolygons AT urrutiajorge onkconvexpolygons |