Triangulations intersect nicely

DOI10.1007/BF02712872zbMath0857.68110MaRDI QIDQ1816461

Siu-Wing Cheng, M. Taschwer, Franz Aurenhammer, Yin-Feng Xu, Günter Rote, Naoki Katoh, Oswin Aichholzer

Publication date: 18 February 1997

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

matchinggreedy triangulation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Related Items

Number of Crossing-Free Geometric Graphs vs. Triangulations ⋮ Drawing outerplanar minimum weight triangulations ⋮ ONLINE ROUTING IN CONVEX SUBDIVISIONS ⋮ Constrained independence system and triangulations of planar point sets ⋮ Matching edges and faces in polygonal partitions ⋮ A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations ⋮ On \(\beta\)-skeleton as a subgraph of the minimum weight triangulation ⋮ The drawability problem for minimum weight triangulations ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A space efficient greedy triangulation algorithm
• Computing a subgraph of the minimum weight triangulation
• Flipping edges in triangulations
• The greedy triangulation can be computed from the Delaunay triangulation in linear time
• Some properties of basic families of subsets
• Fast greedy triangulation algorithms.
• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
• Comments on bases in dependence structures
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Constrained independence system and triangulations of planar point sets