Close this search box.

Geometric Algorithms, Software Workshop, Spring 1997

Workshop (sadna)

Location: Schreiber Building, room 114

Dan Halperin, [email protected]
Office hours: Wednesday, 19:00–20:00
Micha Sharir, [email protected]
Office hours by appointment

We propose projects in the following areas:

  • robot motion planning (simulation and/or for a real mobile robot)
  • geometric molecular modeling
  • shape reconstruction

All projects require implementation of geometric algorithms, graphic display of input and output, and interaction with the user, both graphic and textual.

In the first three meetings we will give an overview of the projects’ topics, one meeting per topic. The fourth meeting (12/03) is devoted to presentation of auxiliary software tools, mainly for geometric computing and graphic display; we will also have a brief demo of the mobile robot capabilities and of some of the existing software tools. In the fifth meeting (19/03) the participating students will present their choice of projects and rough work-plans. For the same meeting students need to submit a brief description (about two pages long) of their plans including a proposal for a prototype.

We recommend to form teams of three students each. Other team sizes are negotiable. By 19/03 the division into teams should of course be agreed upon.

There will not be meetings of the entire class after 19/03. For the rest of the semester we will meet with each of the teams separately.

The submission of the project is in two steps:

  1. May 28, 1997: prototype and its user manual
  2. September 1, 1997: submission of the full project, including full user manual and programming guide


Below we propose a few projects. Students are welcome to propose other projects in the spirit of the SADNA

  • Motion planning for a polygon in a polygonal environment: exact algorithm for translation, and approximate for rotation
  • motion planning for a robot with many degrees of freedom using probabilistic roadmap
  • Motion planning for the mobile robot in the robotics lab
  • Geometric molecular modeling, on-line computation of volume overlap between two molecules
  • Computing the curve implied by a given set of points in the plane (using Voronoi diagram and Delaunay triangulation)
  • Computing the alpha-shape of a set of points
  • Reconstructing a three-dimensional object out of two-dimensional cross-sections

Yair Oz - Webcreator


Skip to content