Computing the minimum weight triangulation of a set of linearly ordered points

DOI10.1016/0020-0190(92)90129-JMaRDI QIDQ1198019zbMATH OpenOpenAlexFDO

Authors David Rappaport, Henk Meijer

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90129-j

zbMATH Keywords

triangulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

We describe an \(O(n^ k)\) time and space algorithm to obtain a minimum weight triangulation of a set of linearly ordered points.

Cites work

• A note on Delaunay and optimal triangulations
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimal Triangulations of Polygonal Domains
• The greedy and Delaunay triangulations are not bad in the average case

Cited in

(6)

• Drawing outerplanar minimum weight triangulations
• Computing the weight distribution of a set of points obtained by scaling, shifting, and truncating a lattice
• Minimum convex partition of a constrained point set
• A lower bound for -skeleton belonging to minimum weight triangulations
• The drawability problem for minimum weight triangulations
• A new subgraph of minimum weight triangulations

This page was built for publication: Computing the minimum weight triangulation of a set of linearly ordered points

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