Abstract
We address the problem of dynamic maintenance of 2-centers in the plane under rectilinear metric.We present two algorithms for the continuous and discrete versions of the problem. We show that rectilinear 2-centers can be maintained in O(log2 n) time. We give an algorithm for semi-dynamic (either insertions only or deletions only) maintenance of the discrete 2-centers in O(log n log m) amortized time where n is the number of customer points and m is the number of possible locations of centers.
Chapter PDF
Similar content being viewed by others
References
M. de Berg, M. van Kreveld, M. Overmars, O. Schwartzkopf Computational Geometry, Algorithms and Applications, Springer-Verlag, 1997.
S. Bespamyatnikh and D. Kirkpatrick, “Rectilinear 2-center problems”, in Proc. of 11th Can. Conf. Comp. Geom., pp. 68–71, 1999.
S. Bespamyatnikh and M. Segal, “Rectilinear static and dynamic discrete 2-center problems”, in Int. Jour. of Math. Algorithms, to appear.
Z. Drezner, “On the rectangular p-center problem”, Naval Res. Logist. Q., 34, pp. 229–234, 1987.
F. P. Preparata and M. I. Shamos, “Computational Geometry: An Introduction”, Springer-Verlag, 1990.
M. Segal, “Lower bounds for covering problems”, manuscript, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bespamyatnikh, S., Segal, M. (2001). Fast Maintenance of Rectilinear Centers. In: Alexandrov, V.N., Dongarra, J.J., Juliano, B.A., Renner, R.S., Tan, C.J.K. (eds) Computational Science — ICCS 2001. ICCS 2001. Lecture Notes in Computer Science, vol 2073. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45545-0_73
Download citation
DOI: https://doi.org/10.1007/3-540-45545-0_73
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42232-7
Online ISBN: 978-3-540-45545-5
eBook Packages: Springer Book Archive