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: You can download the paper from here.

15. (Yuval Leshem) Implement the two dimensional kd-tree.
• Computational Geometry: Algorithms and Applications, Chapter 5.
In addition, implement the kd-tree for arbitrary dimension.
16. (Oren Yardeni) Convexity games: Given a set of points, how many GOMIOT one need to put to cover all points. Joe Mitchel at al. paper. Implment a log(n) approximation algorithm.
17. (Danny Cohen) Visibility graph and motion planning.
18. (Irit Kheifets) Given a set of axis parallel rectangles in the place - check if they cover the unit square. Efficiently.
19. (Natsha Kriemer) TSP - Implement several hueristics & approximation algorithm for the TSP problem.
For some of thos things I have an idea what I want the applet to do, but part of your work in the workshop will be to design applet deciding what to show and how to show it.
Last modified: Thu Jul 2 14:55:03 GMT+0300 1998