Article

Optimally cutting a surface into a disk

Authors:

Sariel Har-PeledAuthors Info & Claims

SCG '02: Proceedings of the eighteenth annual symposium on Computational geometry

Pages 244 - 253

https://doi.org/10.1145/513400.513430

Published: 05 June 2002 Publication History

Abstract

We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n ^O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log² g)-approximation of the minimum cut graph in O(g ² n log n) time.

References

[1]

U. Axen and H. Edelsbrunner. Auditory Morse analysis of triangulated manifolds. Mathematical Visualization, 223--236, 1998. Springer-Verlag.

[2]

C. Bennis, J.-M. Vézien, G. Iglésias, and A. Gagalowicz. Piecewise surface flattening for non-distorted texture mapping. Computer Graphics 25:237--246, 1991. Proc. SIGGRAPH '91.

Digital Library

[3]

M. Bern and P. Plassman. The Steiner problem with edge lengths 1 and 2. Inform. Proc. Lett. 32(4):171--176, 1989.

Digital Library

[4]

N. Biggs. Constructions for cubic graphs with large girth. Elec. J. Combin. 5:A1, 1998.

[5]

J. Blömer. Computing sums of radicals in polynomial time. Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., 670--677, 1991.

Digital Library

[6]

S. Chari, P. Rohatgi, and A. Srinivasan. Randomness-optimal unique element isolation with applications to perfect matching and related problems. SIAM J. Comput. 24(5):1036--1050, 1995.

Digital Library

[7]

T. Dey, H. Edelsbrunner, and S. Guha. Computational topology. Advances in Discrete and Computational Geometry, 109--143, 1999. Contemporary Mathematics 223, American Mathematical Society.

[8]

T. K. Dey and S. Guha. Transforming curves on surfaces. J. Comput. Sys. Sci. 58:297--325, 1999.

Digital Library

[9]

T. K. Dey and H. Schipper. A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete Comput. Geom. 14:93--110, 1995.

Digital Library

[10]

E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik 1:269--271, 1959.

Digital Library

[11]

R. G. Downey and M. R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer-Verlag, 1999.

Digital Library

[12]

S. Dreyfus and R. Wagner. The Steiner problem in graphs. Networks 1:195--207, 1971.

[13]

D. Eppstein. Seventeen proofs of Euler's formula: V-E+F=2. The Geometry Junkyard, May 2001. http://www.ics.uci.edu/~eppstein/junkyard/euler/.

[14]

M. S. Floater. Parametrization and smooth approximation of surface triangulations. Comput. Aided Geom. Design 14(4):231--250, 1997.

Digital Library

[15]

G. K. Francis and J. R. Weeks. Conway's ZIP proof. Amer. Math. Monthly 106:393--399, 1999. http://new.math.uiuc.edu/zipproof/.

[16]

M. R. Garey, R. L. Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32:835--859, 1977.

Digital Library

[17]

M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32:826--834, 1977.

Digital Library

[18]

S. Haker, S. Angenent, A. Tannenbaum, R. Kikinis, G. Sapiro, and M. Halle. Conformal surface parameterization for texture mapping. IEEE Trans. Visualizat. Comput. Graph. 6(2):181--187, 2000.

Digital Library

[19]

M. Hallett and T. Wareham. A compendium of parameterized compplexity results. SIGACT News 25(3):122--123, 1994. http://web.cs.mun.ca/~harold/W_hier/compendium.html.

Digital Library

[20]

M. Hanan. On Steiner's problem with rectilinear distance. SIAM J. Appl. Math. 14:255--265, 1966.

[21]

A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. http://www.math.cornell.edu/~hatcher/.

[22]

D. B. Johnson. Efficient algorithms for shortest paths in sparse networks. J. Assoc. Comput. Mach. 24(1):1--13, 1977.

Digital Library

[23]

A. Klivans and D. A. Spielman. Randomness efficient identity testing of multivariate polynomials. Proc. 33rd Annu. ACM Sympos. Theory Comput., 216--223, 2001.

Digital Library

[24]

L. Kou, G. Markowsky, and L. Berman. A fast algorithm for Steiner trees. Acta Inform. 15:141--145, 1981.

Digital Library

[25]

F. Lazarus, M. Pocchiola, G. Vegter, and A. Verroust. Computing a canonical polygonal schema of an orientable triangulated surface. Proc. 17th Annu. ACM Sympos. Comput. Geom., 80--89, 2001.

Digital Library

[26]

K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Mathing is as easy as matrix inversion. Combinatorica 7:105--113, 1987.

Digital Library

[27]

J. R. Munkres. Topology, 2nd edition. Prentice-Hall, 2000.

[28]

D. Piponi and G. Borshukov. Seamless texture mapping of subdivision surfaces by model pelting and texture blending. Proc. SIGGRAPH 2000, 471--478, 2000.

Digital Library

[29]

A. Sheffer and E. de Sturler. Surface parameterization for meshing by triangulation flattening. Proc. 9th International Meshing Roundtable, 161--172, 2000. http://www.andrew.cmu.edu/user/sowen/abstracts/Sh742.html.

[30]

J. Stillwell. Classical Topology and Combinatorial Group Theory, 2nd edition. Graduate Texts in Mathematics 72. Springer-Verlag, 1993.

[31]

H. Takahashi and A. Matsuyama. An approximate solution for the network Steiner tree problem. Math. Japonica 24:573--577, 1980.

[32]

W. Thurston. Three-Dimensional Geometry and Topology, Volume 1. Princeton University Press, New Jersey, 1997.

[33]

G. Vegter. Computational topology. Handbook of Discrete and Computational Geometry, chapter 28, 517--536, 1997. CRC Press LLC.

Digital Library

[34]

G. Vegter and C. K. Yap. Computational complexity of combinatorial surfaces. Proc. 6th Annu. ACM Sympos. Comput. Geom., 102--111, 1990.

Digital Library

Cited By

Liu WWang PChen SXin STu CHe YWang W(2024)Towards Geodesic Ridge Curve for Region-wise Linear Representation of Geodesic Distance FieldComputer Aided Geometric Design10.1016/j.cagd.2024.102291(102291)Online publication date: Apr-2024
https://doi.org/10.1016/j.cagd.2024.102291
Zeng SGeng GGao HZhou M(2021)A novel geometry image to accurately represent a surface by preserving mesh topologyScientific Reports10.1038/s41598-021-01722-411:1Online publication date: 19-Nov-2021
https://doi.org/10.1038/s41598-021-01722-4
Campen MBousseau AGutierrez D(2017)Partitioning surfaces into quadrilateral patchesProceedings of the European Association for Computer Graphics: Tutorials10.2312/egt.20171033(1-25)Online publication date: 24-Apr-2017
https://dl.acm.org/doi/10.2312/egt.20171033
Show More Cited By

Index Terms

Optimally cutting a surface into a disk
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces
SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given ...
Optimally Cutting a Surface into a Disk

We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-...
Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '02: Proceedings of the eighteenth annual symposium on Computational geometry

June 2002

330 pages

ISBN:1581135041

DOI:10.1145/513400

Conference Chairs:
Ferran Hurtado
Universitat Politècnica de Catalunya
,
Vera Sacristán
Universitat Politècnica de Catalunya
,
Program Chairs:
Chandrajit Bajaj
University of Texas at Austin
,
Subhash Suri
University of California at Santa Barbara

Copyright © 2002 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG02

Sponsor:

SoCG02: The 18th Annual ACM Symposium on Computational Geometry

June 5 - 7, 2002

Barcelona, Spain

Acceptance Rates

SCG '02 Paper Acceptance Rate 35 of 104 submissions, 34%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
39
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu WWang PChen SXin STu CHe YWang W(2024)Towards Geodesic Ridge Curve for Region-wise Linear Representation of Geodesic Distance FieldComputer Aided Geometric Design10.1016/j.cagd.2024.102291(102291)Online publication date: Apr-2024
https://doi.org/10.1016/j.cagd.2024.102291
Zeng SGeng GGao HZhou M(2021)A novel geometry image to accurately represent a surface by preserving mesh topologyScientific Reports10.1038/s41598-021-01722-411:1Online publication date: 19-Nov-2021
https://doi.org/10.1038/s41598-021-01722-4
Campen MBousseau AGutierrez D(2017)Partitioning surfaces into quadrilateral patchesProceedings of the European Association for Computer Graphics: Tutorials10.2312/egt.20171033(1-25)Online publication date: 24-Apr-2017
https://dl.acm.org/doi/10.2312/egt.20171033
Bobenko ASechelmann SSpringborn B(2016)Discrete Conformal Maps: Boundary Value Problems, Circle Domains, Fuchsian and Schottky UniformizationAdvances in Discrete Differential Geometry10.1007/978-3-662-50447-5_1(1-56)Online publication date: 13-Aug-2016
https://doi.org/10.1007/978-3-662-50447-5_1
Li GLiu L(2013)Geometry curvesGraphical Models10.1016/j.gmod.2013.05.00175:5(265-278)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1016/j.gmod.2013.05.001
Jin MDing NYang Y(2013)Computing shortest homotopic cycles on polyhedral surfaces with hyperbolic uniformization metricComputer-Aided Design10.1016/j.cad.2012.07.01545:2(113-123)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.cad.2012.07.015
Matsuyama TNobuhara STakai TTung TMatsuyama TNobuhara STakai TTung T(2012)3D Video Encoding3D Video and Its Applications10.1007/978-1-4471-4120-4_10(315-341)Online publication date: 2012
https://doi.org/10.1007/978-1-4471-4120-4_10
Dong DLi MLiu YLi XLiao X(2011)Topological detection on wormholes in wireless ad hoc and sensor networksIEEE/ACM Transactions on Networking10.1109/TNET.2011.216373019:6(1787-1796)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1109/TNET.2011.2163730
Bern MHayes B(2010)Origami Embedding of Piecewise-Linear Two-ManifoldsAlgorithmica10.1007/s00453-010-9399-859:1(3-15)Online publication date: 9-Mar-2010
https://doi.org/10.1007/s00453-010-9399-8
Kobayashi YKawarabayashi KMathieu C(2009)Algorithms for finding an induced cycle in planar graphs and bounded genus graphsProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496894(1146-1155)Online publication date: 4-Jan-2009
https://dl.acm.org/doi/10.5555/1496770.1496894
Show More Cited By

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents