Enumerating pseudo-triangulations in the plane
type: Item
instance of: scholarly article
title: Enumerating pseudo-triangulations in the plane
zbMATH Open document ID: 1071.65017
author: Sergey Bereg
published in: Computational Geometry
publication date: 2005-05-12T00:00:00Z
review text: An algorithm for enumerating all pointed pseudo-triangulations of a set of \(n\) points in the plane is presented. It uses flips to generate pseudo-triangulations, it is based on a reverse search technique, and its running time is O\((\log n)\) per pseudo-triangulation. It can be used also to list the vertices of the polytope of pointed pseudo-triangulations. Moreover, it generates a spanning tree of the graph of pseudo-triangulations.
reviewed by: Dana Petcu
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 2167822
zbMATH Keywords: pseudo-triangulations
zbMATH Keywords: flips
zbMATH Keywords: reverse search
zbMATH Keywords: spanning tree
zbMATH Keywords: graph
MaRDI profile type: Publication
full work available at URL: j.comgeo.2004.09.002
OpenAlex ID: W2005421767
cites work: Convexity minimizes pseudo-triangulations
cites work: Algorithms and Data Structures
cites work: Reverse search for enumeration
cites work: An efficient algorithm for enumeration of triangulations
cites work: Q4434784
cites work: Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
cites work: Straightening polygonal arcs and convexifying polygonal cycles
cites work: Introduction to algorithms
cites work: Q4279195
cites work: Flipping edges in triangulations
cites work: Kinetic collision detection for simple polygons
cites work: Maintenance of configurations in the plane
cites work: Topologically sweeping visibility complexes via pseudotriangulations
cites work: THE VISIBILITY COMPLEX
cites work: Q5692723
cites work: Q4717849
DOI: 10.1016/J.COMGEO.2004.09.002
Recommended article: On numbers of pseudo-triangulations
Recommended article: On the number of pseudo-triangulations of certain point sets
Recommended article: Counting triangulations of planar point sets
Recommended article: Parallel enumeration of triangulations
Recommended article: Q4331201
Recommended article: ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS
Recommended article: Combinatorial pseudo-triangulations
Recommended article: Q3115027
Recommended article: Enumerating triangulations by parallel diagonals
Recommended article: Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
description: scientific article; zbMATH DE number 2167822