The dual diameter of triangulations

Matias Korman*, Stefan Langerman, Wolfgang Mulzer, Alexander Pilz, Maria Saumell, Birgit Vogtenhuber

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Let P be a simple polygon with n vertices. The dual graph T of a triangulation T of P is the graph whose vertices correspond to the bounded faces of T and whose edges connect those faces of T that share an edge. We consider triangulations of P that minimize or maximize the diameter of their dual graph. We show that both triangulations can be constructed in O(n3log⁡n) time using dynamic programming. If P is convex, we show that any minimizing triangulation has dual diameter exactly 2⋅⌈log2⁡(n/3)⌉ or 2⋅⌈log2⁡(n/3)⌉−1, depending on n. Trivially, in this case any maximizing triangulation has dual diameter n−2. Furthermore, we investigate the relationship between the dual diameter and the number of ears (triangles with exactly two edges incident to the boundary of P) in a triangulation. For convex P, we show that there is always a triangulation that simultaneously minimizes the dual diameter and maximizes the number of ears. In contrast, we give examples of general simple polygons where every triangulation that maximizes the number of ears has dual diameter that is quadratic in the minimum possible value. We also consider the case of point sets in general position in the plane. We show that for any such set of n points there are triangulations with dual diameter in O(log⁡n) and in Ω(n).

Original languageEnglish
Pages (from-to)243-252
Number of pages10
JournalComputational Geometry
Publication statusPublished - 1 Mar 2018


  • Diameter
  • Dual graph
  • Optimization
  • Simple polygon
  • Triangulation

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'The dual diameter of triangulations'. Together they form a unique fingerprint.

Cite this