My Research Interests

General Research Interests

My research interests lie predominately in the area of Applied Geometric Algorithms, particularly with respect to Computer Graphics Algorithms, Spatial Databases (including GIS), and Computational Metrology.

My current focus is on the further development of the Balanced Aspect Ratio Tree, a data structure, my colleagues and I recently developed. These trees are designed to compete with such well-known trees as the k-d tree, octree, and BBD tree in efficiently approximating range queries, nearest-neighbor queries, half-space queries, etc. in moderately high dimensions. Also, whereas all the structures above (except the BBD tree) are only heuristically efficient, we also prove that ours compete theoretically with the BBD tree providing logarithmic query times.

Implementation comparisons are currently underway as well as further research into external memory and dynamic structures. For further information on this topic, please visit my publications page for references to the recent published papers on BAR trees.

I am also concerned with applying the BAR tree to the computer graphics industry. Currently, I have been working with several colleagues on an approach to take advantage of these structures in maintaining the (dynamic) silhouette of a model. (See also the publications page for a writeup of our video demonstration.)

Although I have left the Center for Geometric Computing, I am still attempting to maintain the GeomNet site. Actually, I am planning on porting it over to the center's Onyx machines. This prototype location provides quick and easy access to a few implemented geometric algorithms, including construction of convex hulls, voronoi diagrams, and delaunay triangulations.

In recent years, there has been a huge influx of many geometric implementations and although many are available, not all are supported by and/or easily transported to, a user's system. In many situations, where one package out of several is desired, testing each of the numerous options for performance for the given problem would become a formidable task. A user would have to indiviually download each one, compile it (if possible), read numerous documentation specs, convert the test input to the proper format, and eventually come to a decision on its performance. GeomNet, on the other hand, provides a stabile solution to this problem. With multiple interfaces including applet code and a forms interface, using and testing geometric software has never been easier. For the end-user, the access is quite simple, input queries are sent to the server in one of many formats, which GeomNet then converts to the appropriate format for the application, and returned in any of a multitude of desired output formats, including basic timing statistics. Work is also being done to transmit actual geomtric code (in Java) over the net to make multiple queries even faster and provide additional options to the users. For the developer, installing new packages onto GeomNet is quite easy. The server written entirely in Java is very easily portable, the one task being compiling the various geometric algorithms desired on the system, which are written in many ways. For further, more detailed information, read publication in IEEE Computing, available also from my publications page, and visit the GeomNet site.

I am also interested in further development of efficient algorithms to solve Computational Metrology problems. In particular, I would like to focus on approximate solutions to many of these optimization problems with the hope of improving both time performance and simplicity. Again, check my publications page for recent progress in this area.

Through the influences of my advisor Michael Goodrich and another colleague Stephen Kobourov, I have become highly interested in graph drawing algorithms. The area is rich in interesting, difficult, and important problems. My thesis work on Balanced Aspect Ratio trees is in fact an outgrowth of a paper we presented in Graph Drawing '98. Since then, we have also done research in maintaining planarity while simplifying graphs and in preserving angular resolution and area using only one bend per edge.