On compatible triangulations with a minimum number of Steiner points

DOI10.1016/J.TCS.2020.06.014MaRDI QIDQ2192383zbMATH OpenOpenAlexFDO

Authors Anna Lubiw, Debajyoti Mondal

Publication date 17 August 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.09086

zbMATH Keywords

compatible triangulationslinear homeomorphismsNP-hardnesspolygonal regions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Two vertex-labelled polygons are emph{compatible} if they have the same clockwise cyclic ordering of vertices. The definition extends to polygonal regions (polygons with holes) and to triangulations---for every face, the clockwise cyclic order of vertices on the boundary must be the same. It is known that every pair of compatible $n$-vertex polygonal regions can be extended to compatible triangulations by adding $O(n^2)$ Steiner points. Furthermore, $Omega(n^2)$ Steiner points are sometimes necessary, even for a pair of polygons. Compatible triangulations provide piecewise linear homeomorphisms and are also a crucial first step in morphing planar graph drawings, aka "2D shape animation". An intriguing open question, first posed by Aronov, Seidel, and Souvaine in 1993, is to decide if two compatible polygons have compatible triangulations with at most $k$ Steiner points. In this paper we prove the problem to be NP-hard for polygons with holes. The question remains open for simple polygons.

Review text

Compatible triangulations are used in computer graphics, e.g. in morphing. Two vertex-labelled polygons are compatible if they have the same clockwise cyclic ordering of vertices. This definition can be extended to polygonal regions and to triangulations. It is known that every pair of compatible \(n\)-vertex polygonal regions can be extended to compatible triangulations by adding the Steiner points. An intriguing open question is to decide if two compatible polygons have compatible triangulations with at most \(k\) Steiner points. In this paper it is proven that this problem is NP-hard for polygons with holes. For the other polygons this question still remains open.

Recommendations

• On compatible triangulations of simple polygons
• Flip distance between two triangulations of a point set is NP-complete
• scientific article; zbMATH DE number 1796958
• Towards compatible triangulations.
• Compatible triangulations and point partitions by series-triangular graphs

Cites work

• Algorithms and Computation
• Applications of the crossing number
• Complexity of some geometric and topological problems
• Constructing pairwise disjoint paths with few links
• Deformations of plane graphs
• Drawing partially embedded and simultaneously planar graphs
• Embedding planar graphs at fixed vertex locations
• How to morph planar graph drawings
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• ISOMORPHIC TRIANGULATIONS WITH SMALL NUMBER OF STEINER POINTS
• On compatible triangulations of simple polygons
• Optimal binary space partitions for segments in the plane
• The complexity of drawing a graph in a polygonal region
• Towards compatible triangulations.

Cited in

(11)

• On compatible triangulations of simple polygons
• Compatible triangulations and point partitions by series-triangular graphs
• An efficient approach for high quality compatible triangulations between polygons
• Quality Triangulations with Locally Optimal Steiner Points
• scientific article; zbMATH DE number 741009 (Why is no real title available?)
• ISOMORPHIC TRIANGULATIONS WITH SMALL NUMBER OF STEINER POINTS
• scientific article; zbMATH DE number 1796958 (Why is no real title available?)
• On Compatible Matchings
• OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS
• Regular triangulations and Steiner points
• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete

This page was built for publication: On compatible triangulations with a minimum number of Steiner points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192383)