Dynamically maintaining configurations in the plane (Detailed Abstract)

ABSTRACT

For a number of common configurations of points (lines) in the plane, we develop datastructures in which insertions and deletions of points (or lines, respectively) can be processed rapidly without sacrificing much of the efficiency of query answering of known static structures for these configurations. As a main result we establish a fully dynamic maintenance algorithm for convex hulls that can process insertions and deletions of single points in only O(log3n) steps or less per transaction, where n is the number of points currently in the set. The algorithm has several intriguing applications, including that one can “peel” a set of n points in only O(log3n) steps and that one can maintain two sets at a costs of only O(log3n) or less per insertion and deletion such that it never takes more than O(log2n) steps to determine whether the two sets are separable by a straight line. Also efficient algorithms are obtained for dynamically maintaining the common intersection of a set of half-spaces and for dynamically maintaining the maximal elements of a set of plane points. The results are all derived by means of one master technique, which is applied repeatedly and which seems to capture an appropriate notion of “decomposability” for configurations.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Barnett, V., The ordering of multivariate data (with discussion), J. Roy. Stat. Soc (A), 139 (1976) 318–354.
• 3: Bentley, J.L., Decomposable searching problems, Inf. Proc. Lett. 8 (1979) 244–251.
• 4: Bentley, J.L. and M.I. Shamos, Divide and conquer for linear expected time, Inf. Proc. Lett. 7 (1978) 87–91.
• 5: Bentley, J.L. and M.I.Shamos, A problem in multivariate statistics: algorithm, data structure and applications, Techn. Rep. CMU-CS-78-110, Carnegie Mellon University (1978).
• 6: Brown, K.Q., Fast intersection of half spaces, Techn. Rep. CMU-CS-78-129, Carnegie Mellon University (1978).
• 7: William F. Eddy, A New Convex Hull Algorithm for Planar Sets, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.398-403, Dec. 1977 [doi>10.1145/355759.355766]
• 8: Graham, R.L., An efficient algorithm for determining the convex hull of a finite planar set, Inf. Proc. Lett. 1 (1972) 132–133.
• 9: Green, P.J. and B.W. Silverman, Constructing the convex hull of a set of points in the plane, Computer J. 22 (1979) 262–266.
• 10: Huber, P.J., Robust Statistics: a review, Annals Math. Statistics 43 (1972), 1041–1067.
• 11: Jarvis, R.A., On the identification of the convex hull of a finite set of points in the plane, Inf. Proc. Lett. 2 (1973) 18–21.
• 12: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 13: D. T. Lee , F. P. Preparata, An Optimal Algorithm for Finding the Kernel of a Polygon, Journal of the ACM (JACM), v.26 n.3, p.415-421, july 1979 [doi>10.1145/322139.322142]
• 14: Overmars, M.H. and J. van Leeuwen, Maintenance of configurations in the plane, Tech. Rep. RUU- CS- 79-9 (in press), Dept. of Computer Science, University of Utrecht, 1979.
• 15: Overmars, M.H. and J. van Leeuwen, Two general methods for dynamizing decomposable searching problems, Techn. Rep. RUU-CS-79-10, Dept. of Computer Science, University of Utrecht, 1979.
• 16: F. P. Preparata, An optimal real-time algorithm for planar convex hulls, Communications of the ACM, v.22 n.7, p.402-405, July 1979 [doi>10.1145/359131.359132]
• 17: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 18: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 19: Saxe, J.B. and J.L. Bentley, Transforming static data structures to dynamic structures, Conf. Rec. 20th Annual IEEE Symp. on Foundations of Computer Science, San Juan, Puerto Rico, Oct. 1979, pp 148–168.
• 20: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 21: Shamos, M.I., Geometry and statistics: problems at the interface, in: J.F. Traub(ed), Recent results and new directions in algorithms and complexity, Acad. Press, New York (1976), pp 251–280.
• 22: Michael Ian Shamos, Computational geometry., 1978
• 23: Shamos, M.I. and D. Hoey, Geometric intersection problems, Conf. Rec. 17th Annual IEEE Symp. on Foundations of Computer Science, Houston, Oct. 1976, pp. 208–215.
• 24: van Emde Boas, P., On the n log n lowerbound for convex hull and maximal vector determination, Rep. 79-13, Dept. of Math., University of Amsterdam (1979).
• 25: van Leeuwen, J. and H.A. Maurer, Dynamic systems of static datastructures, Bericht 42, Institut f. Informationsverarbeitung, TU Graz, 1980.
• 26: van Leeuwen, J. and D. Wood, Dynamization of decomposable searching problems, Techn. Rep. RUU-CS-79-5, Dept. of Computer Sci., University of Utrecht, 1979 (to appear in Inf. Proc. Lett).
• 27: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978
• 28: Andrew C Yao, A lower bound to finding convex hulls, Stanford University, Stanford, CA, 1979

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms