On joint triangulations of two sets of points in the plane

2011/02/07 by Ajit A. Diwan, Diwan, Ajit Arvind, Subir Kumar Ghosh +5 · 1 citation
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Robotics and Sensor-Based Localization #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1102.1235

Abstract

In this paper, we establish two necessary conditions for a joint triangulation of two sets of n points in the plane and conjecture that they are sufficient. We show that these necessary conditions can be tested in O(n³) time. For the problem of a joint triangulation of two simple polygons of n vertices, we propose an O(n³) time algorithm for constructing a joint triangulation using dynamic programming.

Cited by

• On existence of a compatible triangulation with the double circle order type

Related

• Four-connected triangulations of planar point sets
• Flip Distance Between Two Triangulations of a Point-Set is NP-complete
• Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials
• Lattice of Triangulations: the proof and an algorithm
• Flip Distance Between Triangulations of a Simple Polygon is NP-Complete