Enumerating pseudo-triangulations in the plane (Q1776895)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Enumerating pseudo-triangulations in the plane |
scientific article; zbMATH DE number 2167822
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Enumerating pseudo-triangulations in the plane |
scientific article; zbMATH DE number 2167822 |
Statements
Enumerating pseudo-triangulations in the plane (English)
0 references
12 May 2005
0 references
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.
0 references
pseudo-triangulations
0 references
flips
0 references
reverse search
0 references
spanning tree
0 references
graph
0 references
0 references
0.92119557
0 references
0.9154322
0 references
0 references
0.9054309
0 references
0 references
0.9009297
0 references
