Concepedia

Dynamic computational geometry

Mikhail J. Atallah

1983 · 85 citations · 12 references

DOI

Concepts

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.

References

12

An efficient algorith for determining the convex hull of a finite planar set

Ronald Graham · Information Processing Letters · 1972 · 1.7K citations

, , +12

Closest-point problems

Michael Ian Shamos, Dan Hoey · 1975 · 1.1K citations

, , +15

On Finding the Maxima of a Set of Vectors

H. T. Kung, Fabrizio Luccio, F. P. Preparata · Journal of the ACM · 1975 · 913 citations · Full text

, , +6

Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems

Nimrod Megiddo · SIAM Journal on Computing · 1983 · 834 citations

, , +12

Convex hulls of finite sets of points in two and three dimensions

F. P. Preparata, S. J. Hong · Communications of the ACM · 1977 · 706 citations · Full text

, , +15