We explore the problem of transforming plane triangulations using simultaneous
diagonal flips. Wagner showed that any n-vertex plane triangulation can be transformed to any other plane triangulation on equal number of vertices using a finite
sequence of diagonal flips. Later on it has been established that O(n) individual flips
suffice to complete this transformation. Bose et al. showed that the transformation
can also be done in 4 × (
2 /
log 54/53
+ 2 /
log 6/5
) logn + 2 ≈ 327.1 log n simultaneous flips. This
bound is asymptotically tight.
We present two algorithms to improve the leading coefficient of this bound for
transforming any plane triangulation into any other. The first of the two algorithms
lowers this bound down to 4 × (
2 /
log 12/11
+ 2 /
log 9/7
) logn + 2 ≈ 85.8 log n. By processing
and preprocessing the interior and exterior of the triangulation’s Hamiltonian cycle
parallelly in an interlaced fashion, we make further improvement of the algorithm
from ≈ 327.1 log n down to 12 /
log 6/5
logn + 2 ≈ 45.6 log n.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/40499 |
| Date | 13 May 2020 |
| Creators | Kaykobad, M Tanvir |
| Contributors | De Carufel, Jean-Lou |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.0019 seconds