NDLI: Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Please wait, while we are loading the content...

Counting and Enumerating Crossing-free Geometric Graphs

A Framework for Computing the Greedy Spanner

There are Plane Spanners of Maximum Degree 4

New and Improved Spanning Ratios for Yao Graphs

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures

Progressive Geometric Algorithms

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp

The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems

Design of 3D printed mathematical art

Embeddability in the 3-sphere is decidable

The Connect-The-Dots Family of Puzzles: The Video

LiveCG: an Interactive Visualization Environment for Computational Geometry

Trajectory Grouping Structure: the Video

Visualizing hyperbolic Voronoi diagrams

Animation of an Algorithm for Drawing Graphs in 3D

Visualization of Floater and Gotsman's Morphing Algorithm

Geometric kth Shortest Paths: the Applet

Polytope Offsets and Straight Skeletons in 3D

Optimal Geometric Flows via Dual Programs

Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons

A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs

Outerstring graphs are χ-bounded

Improved bounds for the conflict-free chromatic art gallery problem

Linear transformation distance for bichromatic matchings

Delaunay triangulations with disconnected realization spaces

Eliminating Tverberg Points, I. An Analogue of the Whitney Trick

Higher Dimensional Cheeger Inequalities

Incidences between points and lines in R4: Extended Abstract

On triple intersections of three families of unit circles

Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage

Smallest enclosing ball for probabilistic data

Peeling Potatoes Near-Optimally in Near-Linear Time

On the Complexity of Randomly Weighted Voronoi Diagrams

A Census of Plane Graphs with Polyline Edges

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited

Using Convex Relaxations for Efficiently and Privately Releasing Marginals

Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Better embeddings for planar Earth-Mover Distance over sparse sets

Higher-Quality Tetrahedral Mesh Generation for Domains with Small Angles by Constrained Delaunay Refinement

On the reconstruction of convex sets from random normal measurements

Intersection of paraboloids and application to Minkowski-type problems

Efficient Random-Walk Methods for Approximating Polytope Volume

The Persistent Homology of Distance Functions under Random Projection

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Computing Topological Persistence for Simplicial Maps

Induced Matchings of Barcodes and the Algebraic Stability of Persistence

Towards Expressive 3D Modeling: new challenges for geometric computing

Computing the Fréchet distance with shortcuts is NP-hard

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Light spanners for Snowflake Metrics

Continuously Flattening Polyhedra Using Straight Skeletons

Two-Point L1 Shortest Path Queries in the Plane

Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Free Edge Lengths in Plane Graphs

Weight Balancing on Boundaries and Skeletons

Separation by Convex Pseudo-Circles

Euclidean Steiner Shallow-Light Trees

Measuring Distance between Reeb Graphs

Stochastic Convergence of Persistence Landscapes and Silhouettes

The Morse Theory of Čech and Delaunay Filtrations

Gromov-Hausdorff Approximation of Filament Structure Using Reeb-type Graph

Metric Embedding, Hyperbolic Space, and Social Networks

Sampling with Removal in LP-type Problems

Liftings and stresses for planar periodic frameworks

The Opaque Square

The JS-graphs of Join and Split Trees

Distinct distances on algebraic curves in the plane

Lower bounds on geometric Ramsey functions

Curves in Rd intersecting every hyperplane at most d + 1 times

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Content Provider	ACM Digital Library
Author	de Verdière, Éric Colin de Mesmay, Arnaud Hubard, Alfredo
Abstract	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 combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart). Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki from 1993, a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov's systolic inequality for surfaces are essentially equivalent. Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length O(g3/2n1/2) for any triangulated combinatorial surface of genus g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition. Finally, we consider the problem of embedding a cut graph with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of combinatorial map of cut graph, there are some surfaces on which any embedding has length superlinear in the number of triangles of the triangulated combinatorial surface.
Starting Page	335
Ending Page	344
Page Count	10
File Format	PDF
ISBN	9781450325943
DOI	10.1145/2582112.2582127
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Riemannian geometry Cut graph Shortest non-trivial cycle Topological graph theory Edge-width Systole Pants decomposition Computational topology Triangulated surface
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in