World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue — Selected Papers from the 25th International Symposium on Algorithms and Computation; Guest Editors: C. Knauer and M. SmidOpen Access

Planar Matchings for Weighted Straight Skeletons

    We introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist.

    Using our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings.

    A preliminary version appeared at ISAAC’14.

    Communicated by Christian Knauer, Guest Editor


    • 1. O. Aichholzer, F. Aurenhammer, D. Alberts and B. Gärtner , A novel type of skeleton for polygons, J. Universal Comp. Sci. 1 (1995) 752–761. Google Scholar
    • 2. S. Huber , Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice (Shaker Verlag, 2012). Google Scholar
    • 3. O. Aichholzer and F. Aurenhammer , Straight skeletons for general polygonal figures in the plane, Voronoi’s Impact on Modern Sciences II, Vol. 21 (1998), pp. 7–21. Google Scholar
    • 4. D. Eppstein and J. Erickson , Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions, Discr. Comput. Geom. 22 (1999) 569–592. Crossref, ISIGoogle Scholar
    • 5. F. Aurenhammer , Weighted skeletons and fixed-share decomposition, Comput. Geom. Theor. Appl. 40 (2008) 93–101. Crossref, ISIGoogle Scholar
    • 6. J.-H. Haunert and M. Sester , Area collapse and road centerlines based on straight skeletons, GeoInformatica 12 (2008) 169–191. Crossref, ISIGoogle Scholar
    • 7. T. Kelly and P. Wonka , Interactive architectural modeling with procedural extrusions, ACM Trans. Graphics 30 (2011) 14:1–14:15. Crossref, ISIGoogle Scholar
    • 8. R. G. Laycock and A. M. Day , Automatically generating large urban environments based on the footprint data of buildings, Proc. 8th ACM Symp. Solid Modeling and Applications (2003), pp. 346–351. Google Scholar
    • 9. G. Barequet, D. Eppstein, M. T. Goodrich and A. Vaxman , Straight skeletons of three-dimensional polyhedra, Proc. 16th Annual European Symp. Algorithms (2008), pp. 148–160. Google Scholar
    • 10. T. Biedl, M. Held, S. Huber, D. Kaaser and P. Palfrader , Weighted straight skeletons in the plane, Comput. Geom. Theor. Appl. 48 (2015) 120–133. Crossref, ISIGoogle Scholar
    • 11. D. Gale and L. S. Shapley , College admissions and the stability of marriage, Amer. Math. Monthly 69 (1962) 9–15. Crossref, ISIGoogle Scholar
    • 12. T. Fleiner, R. W. Irving and D. F. Manlove , Efficient algorithms for generalized stable marriage and roommates problems, Theor. Comp. Sci. 381 (2007) 162–176. Crossref, ISIGoogle Scholar
    • 13. R. W. Irving , An efficient algorithm for the “stable roommates” problem, J. Algorithms 6 (1985) 577–595. Crossref, ISIGoogle Scholar
    • 14. J. J. Tan , A necessary and sufficient condition for the existence of a complete stable matching, J. Algorithms 12 (1991) 154–178. Crossref, ISIGoogle Scholar
    • 15. J. J. Tan and Y.-C. Hsueh , A generalization of the stable matching problem, Discr. Appl. Math. 59 (1995) 87–102. Crossref, ISIGoogle Scholar
    • 16. H.-C. Chang, J. Erickson and C. Xu , Detecting weakly simple polygons, Proc. 26th Symp. Discrete Algorithms (2015), pp. 1655–1670, arXiv:1407.3340. Google Scholar
    Remember to check out the Most Cited Articles!

    Check out these titles in image analysis!