Dynamic Computational Geometry (Preliminary Version)

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.

Authors

• Mikhail J. Atallah

Keywords

• Computational geometry
• Polynomials
• Algorithm design and analysis
• Terminology
• Arithmetic
• Function Of Time
• Time Instants
• Path Planning
• Convex Hull
• Red Points
• Problem Instances
• Brute Force
• Substring
• Blue Points
• Proof Of The Lemma
• Static Case
• Geometric Objects
• Candidate Pairs
• Point Properties
• Jump Discontinuities