Abstract
A dynamic data structure is given that maintains the minimal distance in a set ofn points ink-dimensional space inO((logn)k log logn) amortized time per update. The size of the data structure is bounded byO(n(logn)k). Distances are measured in the MinkowskiL t -metric, where 1 ≤t ≤ ∞. This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon,Discrete Comput. Geom. 4 (1989), 591–604.
N. Blum and K. Mehlhorn, On the average number of rebalancing operations in weight-balanced trees,Theoret. Comput. Sci. 11 (1980), 303–320.
B. Chazelle and L. J. Guibas, Fractional cascading I: A data structuring technique,Algorithmica 1 (1986), 133–162.
M. T. Dickerson and R. S. Drysdale, Enumeratingk distances forn points in the plane,Proc. 7th ACM Symp. on Comp. Geom., 1991 (to appear).
D. Dobkin and S. Suri, Dynamically computing the maxima of decomposable functions, with applications,Proc. 30th Annual IEEE Symp. on Foundations of Computer Science, 1989, pp. 488–493.
K. Mehlhorn,Data Structures and Algorithms, Volume 1:Sorting and Searching, Springer-Verlag, Berlin, 1984.
K. Mehlhorn and S. Näher, Dynamic fractional cascading,Algorithmica 5 (1990), 215–241.
M. H. Overmars. Dynamization of order decomposable set problems.J. Algorithms 2 (1981), 245–260.
M. H. Overmars,The Design of Dynamic Data Structures, Lecture Notes in Computer Science, Vol. 156, Springer-Verlag, Berlin, 1983.
F. P. Preparata and M. I. Shamos,Computational Geometry, an Introduction, Springer-Verlag, New York, 1985.
J. S. Salowe, Shallow interdistance selection and interdistance enumeration, Manuscript, 1991.
M. Smid, A worst-case algorithm for semi-online updates on decomposable problems, Report A 03/90, Fachbereich Informatik, Universität des Saarlandes, 1990.
M. Smid, Maintaining the minimal distance of a point set in less than linear time, Report A 06/90, Fachbereich Informatik, Universität des Saarlandes, 1990.
K. J. Supowit, New techniques for some dynamic closest-point and farthest-point problems,Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 84–90.
P. M. Vaidya, AnO(n logn) algorithm for the all-nearest-neighbors problem,Discrete Comput. Geom. 4 (1989), 101–115.
Author information
Authors and Affiliations
Additional information
This work was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).
Rights and permissions
About this article
Cite this article
Smid, M. Maintaining the minimal distance of a point set in polylogarithmic time. Discrete Comput Geom 7, 415–431 (1992). https://doi.org/10.1007/BF02187852
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187852