Pseudotriangulations from Surfaces and a Novel Type of Edge Flip

DOI10.1137/S0097539702411368zbMath1041.68105OpenAlexW2022779815MaRDI QIDQ4441896

Oswin Aichholzer, Hannes Krasser, Franz Aurenhammer, Peter Brass

Publication date: 8 January 2004

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539702411368

zbMATH Keywords

pseudotriangulationlocally convex functionflip distancesurface realizationconstrained regular complexpolytope representation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Combinatorial complexity of geometric structures (52C45)

Related Items

Resolving Loads with Positive Interior Stresses ⋮ Connecting colored point sets ⋮ Convexity minimizes pseudo-triangulations ⋮ The stochastic walk algorithms for point location in pseudo-triangulations ⋮ On minimum weight pseudo-triangulations ⋮ Matching edges and faces in polygonal partitions ⋮ Gray code enumeration of plane straight-line graphs ⋮ Flips in planar graphs ⋮ Flips in edge-labelled pseudo-triangulations ⋮ Pre-triangulations and liftable complexes ⋮ On the number of pseudo-triangulations of certain point sets ⋮ Triangulations without pointed spanning trees ⋮ General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties ⋮ Flip Algorithm for Segment Triangulations ⋮ 3-Colorability of Pseudo-Triangulations ⋮ Transforming spanning trees and pseudo-triangulations ⋮ FLIPS IN COMBINATORIAL POINTED PSEUDO-TRIANGULATIONS WITH FACE DEGREE AT MOST FOUR