×

Minimizing the diameter of a spanning tree for imprecise points. (English) Zbl 1390.68722

Summary: We study the diameter of a spanning tree, i.e., the length of its longest simple path, under the imprecise points model, in which each point is assigned its own occurrence region instead of an exact location. We prove that the minimum diameter of a spanning tree of \(n\) points each of which is selected from its respective disk (or axis-parallel square) is polynomial-time computable, contrasting with the fact that minimizing the cost of a spanning tree, i.e. the sum of its edge lengths, for imprecise points is known to be NP-hard. This difference is very interesting since for exact points minimizing the cost seems faster than minimizing the diameter [\(O(n\log n)\) versus almost cubic running time]. As the first work regarding the minimum diameter of a spanning tree for imprecise points, our main objective is to investigate essential properties that distinguish the problem from NP-hard instead of minimizing the running time [\(O(n^9)\) for general disks or \(O(n^6)\) for unit ones]. Our algorithm mainly utilizes farthest-site Voronoi diagrams for disks and axis-parallel squares, and these diagrams would have their own merits.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggarwal, A., Guibas, L.J., Saxe, J.B., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discret. Comput. Geom. 4, 591-604 (1989) · Zbl 0696.68045 · doi:10.1007/BF02187749
[2] Aurenhammer, F., Klein, R., Lee, D.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013) · Zbl 1295.52001 · doi:10.1142/8685
[3] Borwein, J.M., Borwein, P.B.: Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, vol. 23. Wiley, New York (1987) · Zbl 0611.10001
[4] Buchin, K., Löffler, M., Morin, P., Mulzer, W.: Preprocessing imprecise points for Delaunay triangulation: simplified and extended. Algorithmica 61(3), 674-693 (2011) · Zbl 1225.68263 · doi:10.1007/s00453-010-9430-0
[5] Chan, T.M.: Semi-online maintenance of geometric optima and measures. SIAM J. Comput. 32(3), 700-716 (2003) · Zbl 1046.68111 · doi:10.1137/S0097539702404389
[6] Cheong, O., Everett, H., Glisse, M., Gudmundsson, J., Hornus, S., Lazard, S., Lee, M., Na, H.: Farthest-polygon voronoi diagrams. Comput. Geom. 44(4), 234-247 (2011) · Zbl 1210.65055 · doi:10.1016/j.comgeo.2010.11.004
[7] Clarkson, K.L., Shor, P.W.: Application of random sampling in computational geometry, II. Discret. Comput. Geom. 4, 387-421 (1989) · Zbl 0681.68060 · doi:10.1007/BF02187740
[8] De Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Computational Geometry. Springer, Berlin (2000) · Zbl 0939.68134 · doi:10.1007/978-3-662-04245-8
[9] Devillers, O.: Delaunay triangulation of imprecise points, preprocess and actually get a fast query time. J. Comput. Geom. 2(1), 30-45 (2011) · Zbl 1404.68187
[10] Disser, Y., Mihalák, M., Montanari, S., Widmayer, P.: Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods. In: ISCO, pp. 208-220 (2014) · Zbl 1445.68158
[11] Dorrigiv, R., Fraser, R., He, M., Kamali, S., Kawamura, A., López-Ortiz, A., Seco, D.: On minimum-and maximum-weight minimum spanning trees with neighborhoods. In: Proceedings of 10th International Workshop on Approximation and Online Algorithms, pp. 93-106 (2012) · Zbl 1394.68415
[12] Ezra, E., Mulzer, W.: Convex hull of points lying on lines in time after preprocessing. Comput. Geom. 46(4), 417-434 (2013) · Zbl 1262.65031 · doi:10.1016/j.comgeo.2012.03.004
[13] Fiala, J., Kratochvíl, J., Proskurowski, A.: Systems of distant representatives. Discret. Appl. Math. 145(2), 306-316 (2005) · Zbl 1084.05059 · doi:10.1016/j.dam.2004.02.018
[14] Gudmundsson, J., Haverkort, H.J., Park, S., Shin, C., Wolff, A.: Facility location and the geometric minimum-diameter spanning tree. Comput. Geom. 27(1), 87-106 (2004) · Zbl 1038.65014 · doi:10.1016/j.comgeo.2003.07.007
[15] Guibas, L.J., Salesin, D., Stolfi, J.: Constructing strongly convex approximate hulls with inaccurate primitives. Algorithmica 9(6), 534-560 (1993) · Zbl 0797.68158 · doi:10.1007/BF01190154
[16] Ho, J., Lee, D.T., Chang, C., Wong, C.K.: Minimum diameter spanning trees and related problems. SIAM J. Comput. 20(5), 987-997 (1991) · Zbl 0749.68042 · doi:10.1137/0220060
[17] Jadhav, S., Mukhopadhyay, A., Bhattacharya, B.K.: An optimal algorithm for the intersection radius of a set of convex polygons. J. Algorithms 20(2), 244-267 (1996) · Zbl 0852.68033 · doi:10.1006/jagm.1996.0013
[18] Klein, R.: Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science, vol. 400. Springer, Berlin (1989) · Zbl 0699.68005 · doi:10.1007/3-540-52055-4
[19] Klein, R., Lingas, A.: Hamiltonian abstract Voronoi diagrams in linear time. In: Proceedings of 5th International Symposium on Algorithms and Computation, pp. 11-19 (1994) · Zbl 0953.68604
[20] Liu, C., Montanari, S.: Minimizing the diameter of a spanning tree for imprecise points. In: Proceedings of 26th International Symposium on Algorithms and Computation, pp. 381-392 (2015) · Zbl 1382.68266
[21] Löffler, M., Mulzer, W.: Unions of onions: preprocessing imprecise points for fast onion decomposition. J. Comput. Geom. 5(1), 1-13 (2014) · Zbl 1404.68196
[22] Löffler, M., Snoeyink, J.: Delaunay triangulation of imprecise points in linear time after preprocessing. Comput. Geom. 43(3), 234-242 (2010) · Zbl 1177.65037 · doi:10.1016/j.comgeo.2008.12.007
[23] Löffler, M., van Kreveld, M.J.: Largest and smallest convex hulls for imprecise points. Algorithmica 56(2), 235-269 (2010) · Zbl 1185.65036 · doi:10.1007/s00453-008-9174-2
[24] Löffler, M., van Kreveld, M.J.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. 43(4), 419-433 (2010) · Zbl 1208.65029 · doi:10.1016/j.comgeo.2009.03.007
[25] Mehlhorn, K., Meiser, S., Rasch, R.: Furthest site abstract voronoi diagrams. Int. J. Comput. Geom. Appl. 11(6), 583-616 (2001) · Zbl 1074.68643 · doi:10.1142/S0218195901000663
[26] Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. J. Comput. Syst. Sci. 23(2), 166-204 (1981) · Zbl 0474.68082 · doi:10.1016/0022-0000(81)90012-X
[27] Sharir, M.: The clarkson-shor technique revisited and extended. Comb. Probab. Comput. 12(2), 191-201 (2003) · Zbl 1031.60011 · doi:10.1017/S0963548302005527
[28] Spriggs, M.J., Keil, J.M., Bespamyatnikh, S., Segal, M., Snoeyink, J.: Computing a \[(1+\epsilon\] ϵ)-approximate geometric minimum-diameter spanning tree. Algorithmica 38(4), 577-589 (2004) · Zbl 1138.68477 · doi:10.1007/s00453-003-1056-z
[29] van Kreveld, M.J., Löffler, M., Mitchell, J.S.B.: Preprocessing imprecise points and splitting triangulations. SIAM J. Comput. 39(7), 2990-3000 (2010) · Zbl 1211.65024 · doi:10.1137/090753620
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.