Abstract
We present a fixed-parameter algorithm which computes for a set P of n points in the plane in \(O(2^{c \sqrt{k} \log k} \cdot k \sqrt{k} n^3)\) time a minimum weight triangulation. The parameter k is the number of points in P that lie in the interior of the convex hull of P and \(c = (2 + \sqrt{2})/(\sqrt{3} -- \sqrt{2}) < 11\).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ajtai, M., Chvátal, V., Newborn, M., Szemerédi, E.: Crossing-free subgraphs. Annals of Discrete Mathematics 12, 9–12 (1982)
Alber, J., Fernau, H., Niedermeier, R.: Graph separators: a parameterized view. Journal of Computer and System Sciences 67, 808–832 (2003)
Deineko, V.G., Hoffmann, M., Okamoto, Y., Woeginger, G.J.: The traveling salesman problem with few inner points. Operations Research Letters 34(1), 106–110 (2006)
Dickerson, M.T., McElfresh, S.A., Montague, M.H.: New algorithms and empirical findings on minimum weight triangulation heuristics. In: Proc. Symposium on Computational Geometry, pp. 238–247. ACM Press, New York (1995)
Djidjev, H.N., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta Informatica 34, 231–243 (1997)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Grantson, M.: Fixed-parameter algorithms and other results for optimal partitions. Licentiate Thesis, Lund University, Sweden (2004)
Grantson, M., Borgelt, C., Levcopoulos, C.: A fixed parameter algorithm for minimum weight triangulation: Analysis and experiments. Technical Report LU-CS-TR:2005-234, Lund University, Sweden (2005)
Grantson, M., Borgelt, C., Levcopoulos, C.: Minimum weight triangulation by cutting out triangles. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 984–994. Springer, Heidelberg (2005)
Grantson, M., Levcopoulos, C.: A fixed-parameter algorithm for the minimum number convex partition problem. In: Akiyama, J., Kano, M., Tan, X. (eds.) JCDCG 2004. LNCS, vol. 3742, pp. 83–94. Springer, Heidelberg (2005)
Hoffmann, M., Okamoto, Y.: The minimum weight triangulation problem with few inner points. Computational Geometry 34(3), 149–158 (2006)
Hwang, R.Z., Chang, R.C., Lee, R.C.T.: The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica 9, 398–423 (1993)
Kyoda, Y., Imai, K., Takeuchi, F., Tajima, A.: A branch-and-cut approach for minimum weight triangulation. In: Leong, H.-V., Jain, S., Imai, H. (eds.) ISAAC 1997. LNCS, vol. 1350, pp. 384–393. Springer, Heidelberg (1997)
Levcopoulos, C., Krznaric, D.: Quasi-greedy triangulations approximating the minimum weight triangulation. In: Proc. Symposium on Discrete Algorithms, pp. 392–401. ACM Press, New York (1996)
Lingas, A.: Subexponential-time algorithms for minimum weight triangulation and related problems. In: Proc. Canadian Conference on Computational Geometry (1998)
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 177–189 (1979)
Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM Journal on Computing 9, 615–627 (1980)
Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences 32, 265–279 (1986)
Mulzer, W., Rote, G.: Minimum weight triangulation is NP-hard. In: Proc. Symposium on Computational Geometry, pp. 1–10. ACM Press, New York (2006)
Plaisted, D.A., Hong, J.: A heuristic triangulation algorithm. Journal of Algorithms 8, 405–437 (1987)
Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation. In: Proc. Symposium on Theory of Computing, pp. 316–325. ACM Press, New York (2006)
Sharir, M., Welzl, E.: On the number of crossing-free matchings (cycles, and partitions). In: Proc. Symposium on Discrete Algorithms, pp. 860–869. ACM Press, New York (2006)
Spillner, A.: A faster algorithm for the minimum weight triangulation problem with few inner points. In: Proc. Algorithms and Complexity in Durham Workshop, pp. 135–146. KCL Publications (2005)
Spillner, A.: Optimal convex partitions of point sets with few inner points. In: Proc. Canadian Conference on Computational Geometry, pp. 34–37 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Knauer, C., Spillner, A. (2006). A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators. In: Fomin, F.V. (eds) Graph-Theoretic Concepts in Computer Science. WG 2006. Lecture Notes in Computer Science, vol 4271. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11917496_5
Download citation
DOI: https://doi.org/10.1007/11917496_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-48381-6
Online ISBN: 978-3-540-48382-3
eBook Packages: Computer ScienceComputer Science (R0)