In my research, I have studied problems that arise in computational geometry and related areas, especially those motivated by applications in Geographic Information Science (GIS), computer graphics, robotics, and pattern matching. There has been extensive research in computational geometry on various fundamental problems in these, and similar domains. Algorithms developed for such problems by practitioners in these areas tend to be efficient mainly for their typical inputs, and they might be inefficient for more complicated inputs. On the other hand, techniques used in computational geometry are proved to be valid and theoretically efficient even in worst cases. Unfortunately, they are too often difficult to implement or slow in practice. These drawbacks have limited the widespread use of computational geometry techniques in fulfilling the practical needs of computer graphics, robotics, and GIS applications. In my research, I focus on bridging this gap between practice and theory by developing algorithms whose correctness and bounds are proven, yet are simple to implement and perform efficiently on real-world inputs. More particularly, I have done active research in the following areas;
I now provide a short description of my research interests and activities in these areas.
Geometric pattern matching I have been interested in problems of
geometric pattern matching for a long time. I have presented algorithms
for matching shapes when the Hausdorff distance is used as the similarity
measure [A5,A8,C2]1,
and I became curious about finding alternative ways to measure similarity.
Despite its usefulness and its common use, the Hausdorff distance suffers
in certain cases, from many drawbacks. I studied the bottleneck matching
as an alternative, and proposed efficient algorithms for computing this
measure. See the papers [B9,A9] for further discussion.
Recently, I have been mainly interested in matching sets of segments, especially where these segments belong to certain orientations. These problems are motivated by constructing models of environments using mobile robots, where a sequence of different pictures of the environment need to be aligned. The paper [D1] describes several techniques obtained for these problems.
GIS and spatial data structures GIS is one of the many fields in
which computational geometry tools have contributed significantly. During
the last couple of years, I have developed a growing interest in GIS, and
its relationship to computational geometry. I investigated the quad-tree,
which is one of the most important and popular data structures in GIS and
computer graphics. I have developed several algorithms for common operations
on quad-trees. The paper [A11,B17] describing these and other algorithms
has been accepted for publication in the Special Issue on GIS of Algorithmica.
I attended the Dagstuhl workshop on computational cartography in September
1999. I have started collaborating with Prof. John Radke, the head of AEGIS
(Applied Environmental Geographic Information Science), a GIS research
laboratory in the University of California at Berkeley, and we are currently
considering submitting a research proposal together. Clearly, GIS is one
of the areas where I predict more significant contribution.
Algorithms for mobile robots During the last year, I have been a
member of the autonomous observer project in Stanford Robotics Laboratory
in the Computer Science Department. The main purpose of this project is
to deploy autonomous mobile robots which can be sent into an unknown building
to study and map their environment, seek interesting targets inside the
building and track them as they move. The questions arising for this task
lie at the interface between robotics, computer vision and computational
geometry. I am interested in both the theoretical and practical aspects
of these questions. On the theoretical side, I am interested in obtaining
algorithms whose correctness and optimality are guaranteed. On the practical
side, I implement these algorithms on the actual robots, and engineer the
algorithms to the properties of the robots and the sensors. The paper [B18]
describes some of the practical problems solved, and the papers [B20,D1]
discuss relevant theoretical issues.
Algorithms for Realistic input models: There have been extensive
studies in the computational geometry community to obtain wide and general
classes of inputs which capture realistic data, yet have ``nice'' combinatorial
properties. The goal is to develop algorithms (either by tailoring known
algorithms or by inventing new ones) that are easy to implement and run
fast on these classes of inputs.
In many cases, the worst case scenario for an algorithm is exhibited only for input objects that are long and ``skinny'', and these seldom appear in realistic scenarios. This phenomenon has given rise to the notion of fatness. A convex object C is called fat if the radius of the smallest ball enclosing C is not ``much larger'' than the largest ball enclosed inside C. For non-convex objects the definition is more involved. I have intensively studied problems where fat objects are involved. In a series of papers with colleagues ([A10,A11,A12,A14,B16]), I have developed efficient algorithms for different variants of fatness, and also show that known algorithms can be executed efficiently for fat objects.
In summary, I have both a strong background in geometric algorithms and
a strong interest in practical applications of geometric techniques. This
combination allows me to collaborate with practitioners in many different
areas, giving me the ability to do research that is both practically relevant
and important and theoretically significant. I envision (and wish) that
my future research will continue to focus on contributing in this way to
the areas mentioned above, as well as others, by obtaining algorithms that
perform efficiently in practice and have excellent theoretical properties.