Workshop in Computational Geometry - Projects

# Workshop in Computational Geometry - Projects

Here is a list of things that might serve as a base for a project in the workshop:
1. Constructing epsilon-spanners in the plane.
2. (taken) Computing medial axis.
3. Solving the 2-center, 3-center problem, rectalinear center, \$p\$-piercing problem.
4. Random convex hull in the plane? The connection to discrete hull?
5. (taken) BSP - demo in two dimensions. And something additional...
6. k-level games: compute the k level, compute the k set, compute the k-set graph, counting all kind of strange featues. Implement k set walk (see Alt paper).
7. range tree
8. (Michael Kleyman)Gaurding an Art Gallery
9. (Ofer Belinsky) Convexity games revisited - Given a simple polygon in the plane decompose it into a minimal number of convex polygons. Implement a simple factor 2 approximation.
10. (Nir Efrat) For a set of points in the plane. Compute:
1. Diameter.
2. Minimal area rectangle
3. Minimal circumference of rectangle containing the points
4. Width
11. (Ori Hartstein) Point location using history tree (i.e. vertical ray shooting among lines).
12. (Evgeny Gonopolsky) Linear Programming in the plane.
• Computational Geometry: Algorithms and Applications, Chapter 4.
In addition, also to implement the linear programming algorithm of Megiddo.
13. (Yael Oren) Implement the Voronoi diagram algorithm using the parabolas sweeping algorithm. Description of the algorith:
• Computational Geometry: Algorithms and Applications, Chapter 7.
• S.J. Fortune, A sweepline algorithm for Voronoi diagrams, Algorithmica, 2 (1987), pp. 153-174.
The implementation should support weighted additive Voronoi diagrams as described in the article.
14. (Amit Rosner) Implement the 2d curve reconstruction algorithm of
N. Amenta and M. Bern and D. Eppstein, The crust and the beta-skeleton: combinatorial curve reconstruction.
The input of the algorithm is just a bunch of points in the plane, the output is the reconstructed curve.

Input: Output: