| Speaker: | Alon Efrat Stanford University | |
|---|---|---|
| Topic: | Target Tracking, Segments Matching, Bottleneck Pattern Matching, and other Geometric Optimization Problems. | |
| Date: | Thursday, March 30, 2000 | |
| Time: | 11:00 AM | |
| Place: | Gould-Simpson, Room 701 |
In the first part of the talk we discuss recent results and ongoing research for problems whose solution uses geometric techniques. These problems include:
- Target tracking problems, where one needs to plan a path for a mobile robot, whose task is to track a moving target inside a building.
- Segment matching. In this problem, a mobile robot moving inside a building produces a series of local maps, each representing a small region of a building, and our task is to align ("mosaic") these maps in order to glue them into a larger map of the whole building. This problem motivated us to present a new measure of similarity between sets of segments, and to obtain algorithms for finding an alignment that maximizes this measure.
In the second part of the talk we discuss the bottleneck matching. Given two shapes A and B, each represented as sets of points, the bottleneck matching between them is defined as a one-to-one matching that minimizes the distance between the farthest pair of points which are matched. This distance reflects how much A is similar to B. We will show algorithms that exactly or approximately compute the bottleneck matching, and describe how to compute translations and rotations that maximize this similarity.
Finally, we discuss some results concerning operations on quad-trees. Quad-trees are among the most popular data structures used for various operations in Computer Graphics and Geographic Information Science. We obtained efficient algorithms for some of these operations, such as point location, dilation, and construction of quad-trees.