12-04-2011, 11:27 AM
aalg10.ppt (Size: 701 KB / Downloads: 127)
Computational geometry
Main goals of the lecture:
to understand the concept of output-sensitive algorithms;
to be able to apply the divide-and-conquer algorithm design technique to geometric problems;
to remember how recurrences are used to analyze the divide-and-conquer algorithms;
to understand and be able to analyze the Jarvis’s march and the divide-and-conquer closest-pair algorithms.
Size of the output
In computational geometry, the size of an algorithm’s output may differ/depend on the input.
Line-intersection problem vs. convex-hull problem
Observation: Graham’s scan running time depends only on the size of the input – it is independent of the size of the output
Gift wrapping
Would be nice to have an algorithm that runs fast if the convex hull is small
Idea: gift wrapping (a.k.a Jarvis’s march)
• 1. Start with the lowest point a, include it in the convex hull
• 2. The next point in the convex hull has to be in the clockwise direction with respect to all other points looking from the current point on the convex hull
• 3. Repeat 2. until a is reached.
Jarvis’s march
How many cross products are computed for this example?
The running time of Jarvis’s march:
Find lowest point – O(n)
For each vertex in the convex hull: n–1 cross-product computations
Total: O(nh), where h is the number of vertices in the convex hull
Output-sensitive algorithms
Output-sensitive algorithm: its running time depends on the size of the output.
When should we use Jarvi’s march instead of the Graham’s scan?
The asymptotically optimal output-sensitive algorithm of Kirkpatrick and Seidel runs in O(n lg h)