1. Convex Hull Algorithm

• O(nlog(n))

2. Divide and Conquer Algorithms

• Upper Hull Binary Search Overmars and van Leeuwan Chan Simple Output-Sensitive Convex Hull Algorithm

3. line-line intersection

4. Bentley-Ottmann plane-sweep algorithm

5. WAVL Tree

6. Polygon Triangulation

7. Linear Programming Divide & Conquer Half Plane intersection

8. Lower Envelopes

9. Davenport-Schinzel sequences

Range Searching K-D trees Planar Point location using persistent search trees Kirkpatricks panar point loacatino method

Arrangements and Duality

Delaunary triangulation random 3-D convex hulls

Windowing data structures.

Priority Search Trees Segment Trees Interval Trees

ToDo:

1. Point
2. Line, Segment, Ray
3. Polygon