Abstract
We construct a new proximity graph, called the Pie Delaunay graph, on a set of n points which is a super graph of Yao graph and Euclidean minimum spanning tree (EMST). We efficiently maintain the Pie Delaunay graph where the points are moving in the plane. We use the kinetic Pie Delaunay graph to create a kinetic data structure (KDS) for maintenance of the Yao graph and the EMST on a set of n moving points in 2-dimensional space. Assuming x and y coordinates of the points are defined by algebraic functions of at most degree s, the structure uses O(n) space, O(nlogn) preprocessing time, and processes O(n 2 λ 2s + 2(n)β s + 2(n)) events for the Yao graph and O(n 2 λ 2s + 2(n)) events for the EMST, each in O(log2 n) time. Here, λ s (n) = nβ s (n) is the maximum length of Davenport-Schinzel sequences of order s on n symbols. Our KDS processes nearly cubic events for the EMST which improves the previous bound O(n 4) by Rahmati et al. [1].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Rahmati, Z., Zarei, A.: Kinetic Euclidean Minimum Spanning Tree in the Plane. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2011. LNCS, vol. 7056, pp. 261–274. Springer, Heidelberg (2011)
Abam, M.A., de Berg, M., Gudmundsson, J.: A simple and efficient kinetic spanner. Comput. Geom. Theory Appl. 43, 251–256 (2010)
Alexandron, G., Kaplan, H., Sharir, M.: Kinetic and dynamic data structures for convex hulls and upper envelopes. Comput. Geom. Theory Appl. 36(2), 144–158 (2007)
Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1997, pp. 747–756. Society for Industrial and Applied Mathematics, Philadelphia (1997)
Kaplan, H., Rubin, N., Sharir, M.: A kinetic triangulation scheme for moving points in the plane. Comput. Geom. Theory Appl. 44(4), 191–205 (2011)
Yao, A.C.C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11(4), 721–736 (1982)
Guibas, L.J., Mitchell, J.S.B.: Voronoi Diagrams of Moving Points in the Plane. In: Schmidt, G., Berghammer, R. (eds.) WG 1991. LNCS, vol. 570, pp. 113–125. Springer, Heidelberg (1992)
Fu, J.J., Lee, R.C.T.: Minimum spanning trees of moving points in the plane. IEEE Trans. Comput. 40(1), 113–118 (1991)
Agarwal, P.K., Eppstein, D., Guibas, L.J., Henzinger, M.R.: Parametric and kinetic minimum spanning trees. In: FOCS, pp. 596–605. IEEE Computer Society (1998)
Basch, J.: Kinetic data structures. PhD Thesis, Stanford University (1999)
Basch, J., Guibas, L.J., Zhang, L.: Proximity problems on moving points. In: Proceedings of the Thirteenth Annual Symposium on Computational Geometry, SCG 1997, pp. 344–351. ACM, New York (1997)
Chew, L.P., Dyrsdale III, R.L.S.: Voronoi diagrams based on convex distance functions. In: Proceedings of the First Annual Symposium on Computational Geometry, SCG 1985, pp. 235–244. ACM, New York (1985)
Agarwal, K.P., Sharir, M.: Davenport–schinzel sequences and their geometric applications. Technical report, Durham, NC, USA (1995)
Kruskal, J.B.: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 7 (1956)
Prim, R.C.: Shortest connection networks and some generalizations. Bell Systems Technical Journal, 1389–1401 (November 1957)
Katoh, N., Tokuyama, T., Iwano, K.: On minimum and maximum spanning trees of linearly moving points. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, SFCS 1992, pp. 396–405. IEEE Computer Society, Washington, DC (1992)
Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362–391 (1983)
Chan, T.M.: On levels in arrangements of curves. Discrete and Computational Geometry 29, 375–393 (2003)
Marcus, A., Tardos, G.: Intersection reverse sequences and geometric applications. J. Comb. Theory Ser. A 113(4), 675–691 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abam, M.A., Rahmati, Z., Zarei, A. (2012). Kinetic Pie Delaunay Graph and Its Applications. In: Fomin, F.V., Kaski, P. (eds) Algorithm Theory – SWAT 2012. SWAT 2012. Lecture Notes in Computer Science, vol 7357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31155-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-31155-0_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31154-3
Online ISBN: 978-3-642-31155-0
eBook Packages: Computer ScienceComputer Science (R0)