Seminar
Lecture: Wednesday, 17:00-19:00, Kaplun 324
Instructor: Dan Halperin, [email protected]
Office hours by appointment
An arrangement of geometric objects is the decomposition of space induced by these objects. An arrangement of a finite collection \(L\) of lines in the plane, for example, is the subdivision of the plane into vertices, edges, and faces induced by the lines in \(L\): a vertex is the intersection point of two lines in \(L\); an edge is a maximal connected portion of a line in \(L\) that is not intersected by any other line in \(L\); and a face is a maximal connected region of the plane not intersected by any line in \(L\). Arrangements of curves and surfaces are fundamental constructs in computational geometry, and they are useful for solving problems in a variety of domains. For a survey of definitions, problems, results and applications of arrangements [psz]
In the seminar we will cover basic techniques for manipulating arrangements, with an emphasis on applications. We will review applications of arrangements to computer vision, robot motion planning, molecular modeling, mechanical assembly planning, and more.
After two introductory meetings (05/11, 12/11), we will follow the schedule below of students presentations (temporary list, stay tuned).
Aspect Graphs (Maintaining Invariants, Sparseness)
- 19.11
- Efficiently computing and representing aspect graphs of polyhedral objects
Z. Gigus, J. Canny and R. Seidel, IEEE Trans. Pattern Anal. Mach. Intell., Vol. 13. no. 6 (1991), 542–551
- Efficiently computing and representing aspect graphs of polyhedral objects
- 26.11
- Sparse arrangements and the number of views of polyhedral scenes
M. de Berg, D. Halperin, M.H. Overmars and M. van Kreveld, International Journal of Computational Geometry and Applications 7 (1997), 175–195
- Sparse arrangements and the number of views of polyhedral scenes
Geometric Modeling of Molecules (“Fatness”, Robustness I)
- 03.12
- Spheres, molecules, and hidden surface removal
D. Halperin and M.H. Overmars, In Proceedings of the 10th ACM Symposium on Computational Geometry, Stony Brook, 1994, pp. 113–122
- Spheres, molecules, and hidden surface removal
- 10.12
- A perturbation scheme for spherical arrangements with application to molecular modeling
D. Halperin and C.R. Shelton, In Proceedings of the 13th ACM Symposium on Computational Geometry, Nice, 1997, pp. 183–192. - Dynamic maintenance of kinematic structures
D. Halperin, J.-C. Latombe and R. Motwani, Robotics Motion and Manipulation, J.-P. Laumond and M. Overmars (eds.), A. K. Peters, 1997, pp. 155–170.
This paper does not directly contain arrangement material, but it raises interesting problems on the dynamic maintenance of arrangements.
- A perturbation scheme for spherical arrangements with application to molecular modeling
Robot Motion Planning (Configuration Space)
- 17.12
- Robot motion planning and the single cell problem in arrangements
D. Halperin, Journal of Intelligent and Robotic Systems, 11 (1994) pp. 45–65 - Computing a face in an arrangement of line segments and related problems
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink, SIAM J. Computing, 1993, pp. 1286–1302
- Robot motion planning and the single cell problem in arrangements
- 24.12
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
K. Kedem, R. Livne, J. Pach and M. Sharir, Discrete Computational Geometry 1 (1986), pp. 59–71 - Combinatorial complexity of translating a box in polyhedral 3-space
D. Halperin and C.-K. Yap, Computational Geometry: Theory and Applications, to appear.
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
Assembly Planning (Motion Space)
- 31.12
- A general framework for assembly planning: The motion space approach
D. Halperin, J.-C. Latombe and R.H. Wilson, Algorithmica, to appear.
- A general framework for assembly planning: The motion space approach
- 7.1.98
- Polyhedral assembly partitioning using maximally covered cells in arrangements of convex polytopes
L. Guibas, D. Halperin, H. Hirukawa, J.-C. Latombe and R.H. Wilson, International Journal of Computational Geometry and Applications, to appear.
- Polyhedral assembly partitioning using maximally covered cells in arrangements of convex polytopes
Part Manipulation (Duality, Zone)
- 14.01
- Orienting polygonal parts without sensors
K.Y. Goldberg, Algorithmica, 10 (1993), pp. 201–225 - The complexity of oblivious plans for orienting and distinguishing polygonal parts
Y.-B. Chen and D. Ierardi, Algorithmica, 14 (1995), pp. 367–397.
- Orienting polygonal parts without sensors
- 21.01
- The area bisectors of a polygon and force equilibria in programmable vector fields
Karl F Böhringer, B.R. Donald and D. Halperin, In Proceedings of the 13th ACM Symposium on Computational Geometry, Nice, 1997, pp. 457–459
The full version [psz]
- The area bisectors of a polygon and force equilibria in programmable vector fields
Robustness II
- 28.01
- Practical segment intersection with finite precision output
J. D. Hobby, Computational Geometry: Theory and Applications, to appear - Snap rounding line segments efficiently in two and three dimensions
M. Goodrich, L. Guibas, J. Hershberger, and P. Tanenbaum, In Proceedings of the 13th ACM Symposium on Computational Geometry, Nice, 1997, pp. 284–293
- Practical segment intersection with finite precision output
- 04.02
- Exact computation of line segment intersections
Chapter 3 in Christoph Burnikel’s Ph.D. Thesis, Saarbr & uumlcken, 1996 - Robust plane sweep for intersecting segments
J.-D. Boissonnat and F.P. Preparata, Technical report No. 3270, INRIA, September 1997
- Exact computation of line segment intersections