Abstract
Approximation algorithms are developed for the diagonal- flip transformation of convex polygon triangulations and equivalently rotation transformation of binary trees. For two arbitrary triangulations in which each vertex is an end of at most d diagonals, Algorithm A has the approximation ratio \(2 - \frac{2}{{4(d - 1)(d + 6) + 1}}.\)For triangulations containing no internal triangles, Algorithm B has the approximation ratio 1.97. Two self-interesting lower bounds on the diagonal-flip distance are also established in the analyses of these two algorithms.
Supported in part by the NSERC Operating Grant OGP0046506, ITRC and a CGAT grant.
Part of the work was done at Waterloo and supported by a CGAT grant.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
D. Aldous, Triangulating the circle, at random. Amer Math. Monthly89(1994), 223–234.
B. DasGupta, X. He, T. Jiang, M. Li, J. Tromp and L. Zhang, On distance between phylogenetic trees. Proc. of the SIAM-ACM 8th Annual Symposium on Discrete Algorithms, 427–436, 1997.
K. Culik and D. Wood, A note on some tree similarity measures, Information Processing Letters15(1982), 39–42.
J.-Y. Cai and M. D. Hirsch, Rotation distance, triangulation of planar surfaces and hyperbolic geometry, Proceeding of the 5th Inter. Symposium on Algorithm and Computation, Lecture Notes in Computer Science, vol. 834, 172–180, 1994.
A. K. Dewdney, Wagner’s theorem for torus graphs, Discrete Math. 4(1973), 139–149.
L. Guibas and J. Hershberger, Morphing simple polygons, Proceeding of the ACM 10th Annual Sym. of Comput. Geometry, 267–276, 1994.
S. Hanke, T. Ottmann and S. Schuierer, The edge-flipping distance of triangulations. Proc. of the European Workshop of Comput. Geometry, 1996. Technical Report 76, Insttut fur Informatik, Universitat Freiburg, 1996.
J. Hershberger and S. Suri, Morphing binary trees. Proceeding of the ACM-SIAM 6th Annual Symposium of Discrete Algorithms, 396–404, 1995.
F. Hurtado, M. Noy, and J. Urrutia, Flipping edges in triangulations, Proc. of the ACM 12th Annual Sym. of Comput. Geometry, 214–223, 1996.
D. Knuth, The art of computer programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973.
D. Knuth, Computer Musings (Videotape): The associative law, or the anatomy of rotations in binary trees, University Video Communications, 1993.
J. Pallo, On rotation distance in the lattice of binary trees, Infor. Proc. Letters25(1987), 369–373.
D. D. Sleator and R. Tarjan, Self-adjusting binary search trees, J. Assoc. Comput. Mach.32(1985), 652–686.
D. D. Sleator, R. Tarjan and W. Thurston, Rotation distance, in T.M. Cover and B. Gopinath eds, Open problems in communication and computation, Springer-Verlag, 1987.
D. D. Sleator, R. Tarjan and W. Thurston, Rotation distance, triangulations, and hyperbolic geometry, Proc. of the 18th Annual ACM Symposium on Theory of Comput., Berkeley, CA., 122–135, 1986. Also appearing on J. of American Math. Soc. 1(1988), No. 3, 647 — 681.
D. D. Sleator, R. Tarjan and W. Thurston, Short encoding of evolving structures, SIAM J. Disc. Math.5(1992), 428–450.
D. Swofford, G. J. Olsen, P. J. Waddell and D. M. Hillis, Phylogenetic Inference, In Molecular Systematics, 2nd Edition, edited by D. M. Hillis, C. Moritz and B. K. Mable, Sinauer Associates, Mass., 1996.
R. E. Tarjan, Data structures and network algorithms, Soc. Indus. Appl. Math., Philadelphia, PA. 1983.
K. Wagner, Bemerkungen zum vierfarbenproblem, J. Deutschen Math.-Verin. 46(1936), 26–32.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, M., Zhang, L. (1998). Better Approximation of Diagonal-Flip Transformation and Rotation Transformation. In: Hsu, WL., Kao, MY. (eds) Computing and Combinatorics. COCOON 1998. Lecture Notes in Computer Science, vol 1449. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68535-9_12
Download citation
DOI: https://doi.org/10.1007/3-540-68535-9_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64824-6
Online ISBN: 978-3-540-68535-7
eBook Packages: Springer Book Archive