More Web Proxy on the site http://driver.im/

research-article

A Faster Algorithm for Computing Straight Skeletons

Authors:

Siu-Wing Cheng,

Antoine VigneronAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 12, Issue 3

Article No.: 44, Pages 1 - 21

https://doi.org/10.1145/2898961

Published: 25 April 2016 Publication History

Abstract

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n(log n)log r) time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected O(nsqrth+ 1 log²n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a nondegenerate polygon in O(n(log n)log r + r^{4/3 + ε}) time for any ε > 0. On degenerate input, our time bound increases to O(n(log n)log r + r^{17/11 + ε}).

References

[1]

A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor. 1989. A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete and Computational Geometry 4, 1, 591--604.

Digital Library

[2]

O. Aichholzer, D. Alberts, F. Aurenhammer, and B. Gärtner. 1995. A novel type of skeleton for polygons. Journal of Universal Computer Science 1, 12, 752--761.

[3]

G. Barequet, M. Goodrich, A. Levi-Steiner, and D. Steiner. 2003. Straight-skeleton based contour interpolation. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 119--127.

Digital Library

[4]

Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. 2008. Computational Geometry: Algorithms and Applications. Springer-Verlag.

[5]

T. Biedl, M. Held, S. Huber, D. Kaaser, and P. Palfrader. 2015. Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications 48, 120--133.

Digital Library

[6]

J. Bowers. 2014. Computing the straight skeleton of a simple polygon from its motorcycle graph in deterministic O (n log n) time. CoRR abs/1405.6260.

[7]

B. Chazelle. 1991. Triangulating a simple polygon in linear time. Discrete and Computational Geometry 6, 5, 485--524.

Digital Library

[8]

S.-W. Cheng, L. Mencel, and A. Vigneron. 2014. A faster algorithm for computing straight skeletons. In Proceedings of the 16th European Symposium on Algorithms (ESA’14). 272--283.

[9]

S.-W. Cheng and A. Vigneron. 2007. Motorcycle graphs and straight skeletons. Algorithmica 47, 2, 159--182.

Digital Library

[10]

F. Chin, J. Snoeyink, and C. A. Wang. 1999. Finding the medial axis of a simple polygon in linear time. Discrete and Computational Geometry 21, 3, 405--420.

[11]

F. Cloppet, J. Oliva, and G. Stamon. 2000. Angular bisector network, a simplified generalized Voronoi diagram: Application to processing complex intersections in biomedical images. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 1, 120--128.

Digital Library

[12]

S. Coquillart, J. Oliva, and M. Perrin. 1996. 3D reconstruction of complex polyhedral shapes from contours using a simplified generalized Voronoi diagram. Computer Graphics Forum 15, 3, 397--408.

[13]

A. Day and R. Laycock. 2003. Automatically generating large urban environments based on the footprint data of buildings. In Proceedings of the 8th ACM Symposium on Solid Modeling and Applications. 346--351.

Digital Library

[14]

E. D. Demaine, M. L. Demaine, and A. Lubiw. 1998. Folding and cutting paper. In Revised Papers from the Japan Conference on Discrete and Computational Geometry. 104--117.

Digital Library

[15]

E. D. Demaine, M. L. Demaine, and A. Lubiw. 1999a. Folding and one straight cut suffice. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. 891--892.

Digital Library

[16]

E. D. Demaine, M. L. Demaine, and J. S. B. Mitchell. 1999b. Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami. In Proceedings of the 15th Annual ACM Symposium on Computational Geometry. 105--114.

Digital Library

[17]

D. Eppstein and J. Erickson. 1999. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. Discrete and Computational Geometry 22, 4, 569--592.

[18]

P. Felkel and Š. Obdržálek. 1998. Straight skeleton implementation. In Proceedings of the 14th Spring Conference on Computer Graphics. 210--218.

[19]

J. Hershberger. 1989. Finding the upper envelope of n line segments in O(n log n) time. Information Processing Letters 33, 4, 169--174.

Digital Library

[20]

S. Huber and M. Held. 2011. Theoretical and practical results on straight skeletons of planar straight-line graphs. In Proceedings of the 27th Symposium on Computational Geometry. 171--178.

Digital Library

[21]

S. Huber and M. Held. 2012. A fast straight-skeleton algorithm based on generalized motorcycle graphs. International Journal of Computational Geometry and Applications 22, 5, 471--498.

[22]

O. Kariv and S. Hakimi. 1979. An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics 37, 3, 539--560.

[23]

T. Kelly and P. Wonka. 2011. Interactive architectural modeling with procedural extrusions. ACM Transactions on Graphics 30, 2, 14:1--14:15.

Digital Library

[24]

A. Vigneron and L. Yan. 2013. A faster algorithm for computing motorcycle graphs. In Proceedings of the 29th Symposium on Computational Geometry. 17--26.

Digital Library

[25]

G. von Peschka. 1877. Kotirte Ebenen: Kotirte Projektionen und Deren Anwendung; Vorträge. Brno: Buschak and Irrgang.

Cited By

Hamedmohseni BRahmati ZMondal D(2023)Emanation Graph: A Plane Geometric Spanner with Steiner PointsGraphs and Combinatorics10.1007/s00373-023-02632-039:2Online publication date: 31-Mar-2023
https://dl.acm.org/doi/10.1007/s00373-023-02632-0
Aurenhammer FLadurner CSteinkogler M(2022)Incremental Construction of Motorcycle GraphsAlgorithms10.3390/a1507022515:7(225)Online publication date: 27-Jun-2022
https://doi.org/10.3390/a15070225
Eder GHeld MPalfrader P(2021)Implementing Straight Skeletons with Exact Arithmetic: Challenges and ExperiencesComputational Geometry10.1016/j.comgeo.2021.101760(101760)Online publication date: Feb-2021
https://doi.org/10.1016/j.comgeo.2021.101760
Show More Cited By

Index Terms

A Faster Algorithm for Computing Straight Skeletons
1. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A faster algorithm for computing motorcycle graphs
SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometry

We present a new algorithm for computing motorcycle graphs that runs in O(n^4/3+ε) time for any ε>0, improving on all previously known algorithms. The main application of this result is to computing the straight skeleton of a polygon. It allows us to ...
A Faster Algorithm for Computing Motorcycle Graphs

We present a new algorithm for computing motorcycle graphs that runs in $$O(n^{4/3+\varepsilon })$$O(n4/3+ ) time for any $$\varepsilon >0$$ >0, improving on all previously known algorithms. The main application of this result is to computing the ...
Theoretical and practical results on straight skeletons of planar straight-line graphs
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

We study straight skeletons and make both theoretical and practical contributions which support new approaches to the computation of straight skeletons of arbitrary planar straight-line graphs (PSLGs). We start with an adequate extension of the concept ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 12, Issue 3

June 2016

408 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2930058

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 April 2016

Accepted: 01 January 2016

Revised: 01 September 2015

Received: 01 November 2014

Published in TALG Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Research Grants Council, Hong Kong, China
KAUST

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
293
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hamedmohseni BRahmati ZMondal D(2023)Emanation Graph: A Plane Geometric Spanner with Steiner PointsGraphs and Combinatorics10.1007/s00373-023-02632-039:2Online publication date: 31-Mar-2023
https://dl.acm.org/doi/10.1007/s00373-023-02632-0
Aurenhammer FLadurner CSteinkogler M(2022)Incremental Construction of Motorcycle GraphsAlgorithms10.3390/a1507022515:7(225)Online publication date: 27-Jun-2022
https://doi.org/10.3390/a15070225
Eder GHeld MPalfrader P(2021)Implementing Straight Skeletons with Exact Arithmetic: Challenges and ExperiencesComputational Geometry10.1016/j.comgeo.2021.101760(101760)Online publication date: Feb-2021
https://doi.org/10.1016/j.comgeo.2021.101760
Barequet GDe MGoodrich M(2021)Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex PolygonsAlgorithmica10.1007/s00453-021-00824-983:7(2245-2272)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s00453-021-00824-9
Eder GHeld MPalfrader P(2019)Recognizing Geometric Trees as Positively Weighted Straight Skeletons and Reconstructing Their InputInternational Journal of Computational Geometry & Applications10.1142/S021819591950008029:03(251-267)Online publication date: 24-Oct-2019
https://doi.org/10.1142/S0218195919500080
Eder GHeld MPalfrader P(2019)Min-/Max-Volume Roofs Induced by Bisector Graphs of Polygonal Footprints of BuildingsInternational Journal of Computational Geometry & Applications10.1142/S021819591850009728:04(309-340)Online publication date: 11-Apr-2019
https://doi.org/10.1142/S0218195918500097
Eder GHeld M(2018)Computing positively weighted straight skeletons of simple polygons based on a bisector arrangementInformation Processing Letters10.1016/j.ipl.2017.12.001132(28-32)Online publication date: Apr-2018
https://doi.org/10.1016/j.ipl.2017.12.001
Aurenhammer FWalzl G(2016)Straight Skeletons and Mitered Offsets of Nonconvex PolytopesDiscrete & Computational Geometry10.1007/s00454-016-9811-556:3(743-801)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00454-016-9811-5

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents