arXiv Open Access 2015

Flips in Edge-Labelled Pseudo-Triangulations

Prosenjit Bose Sander Verdonschot

Lihat Sumber

Abstrak

We show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(n \log c + h \log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.

Topik & Kata Kunci

cs.CG

Penulis (2)

Prosenjit Bose

Sander Verdonschot

Format Sitasi

APA MLA BibTeX

Bose, P., Verdonschot, S. (2015). Flips in Edge-Labelled Pseudo-Triangulations. https://arxiv.org/abs/1512.01485

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2015
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓