Dynamic computational geometry
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 92-99
- https://doi.org/10.1109/sfcs.1983.13
Abstract
We consider problems in computational geometry when every one of the input points is moving in a prescribed manner. We present and analyze efficient algorithms for a number of problems and prove lower bounds for some of them.Keywords
This publication has 11 references indexed in Scilit:
- Lower bounds for algebraic computation treesPublished by Association for Computing Machinery (ACM) ,1983
- A Lower Bound to Finding Convex HullsJournal of the ACM, 1981
- On the Ω(n log n) lower bound for convex hull and maximal vector determinationInformation Processing Letters, 1980
- On the complexity of computations under varying sets of primitivesJournal of Computer and System Sciences, 1979
- Convex hulls of finite sets of points in two and three dimensionsCommunications of the ACM, 1977
- Divide-and-conquer in multidimensional spacePublished by Association for Computing Machinery (ACM) ,1976
- On Finding the Maxima of a Set of VectorsJournal of the ACM, 1975
- Closest-point problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- Geometric complexityPublished by Association for Computing Machinery (ACM) ,1975
- An efficient algorith for determining the convex hull of a finite planar setInformation Processing Letters, 1972