The Edge-Flipping Distance of Triangulations
| dc.creator | Hanke,Sabine | |
| dc.creator | Ottmann,Thomas | |
| dc.creator | Schuierer,Sven | |
| dc.date | 1996 | |
| dc.date.accessioned | 2024-02-06T12:48:26Z | |
| dc.date.available | 2024-02-06T12:48:26Z | |
| dc.description | An edge-flipping operation in a triangulation T of a set of points in the plane is a local restructuring that changes T into a triangulation that differs from T in exactly one edge. The edge-flipping distance between two triangulations of the same set of points is the minimum number of edge-flipping operations needed to convert one into the other. In the context of computing the rotation distance of binary trees Sleator, Tarjan, and Thurston show an upper bound of 2n - 10 on the maximum edge-flipping distance between triangulations of convex polygons with n nodes, n > 12. Using volumetric arguments in hyperbolic 3-space they prove that the bound is tight. In this paper we establish an upper bound on the edge-flipping distance between triangulations of a general finite set of points in the plane by showing that no more edge-flipping operations than the number of intersections between the edges of two triangulations are needed to transform these triangulations into another, and we present an algorithm that computes such a sequence of edge-flipping operations. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-002-08-0570 | |
| dc.identifier | https://lib.jucs.org/article/27276/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/7016 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 2(8): 570-579 | |
| dc.subject | triangulation | |
| dc.subject | edge-flipping operation | |
| dc.subject | flip | |
| dc.subject | edge-flipping distance | |
| dc.subject | rotation distance | |
| dc.title | The Edge-Flipping Distance of Triangulations | |
| dc.type | Research Article |