College of Science & Engineering
Twin Cities
This group's work centers around the design, analysis, implementation, and evaluation of efficient algorithms and data structures for problems defined over a large, discrete set of geometric entities (e.g., points, lines, polygons, polyhedra, etc.). The questions of interest addressed include construction of fundamental geometric structures (e.g., convex hulls, Voronoi diagrams, Delaunay triangulations, skylines, etc.), space- and time-efficient query processing over geometric databases, and optimization over geometric data. Of particular interest are approximation algorithms for high-dimensional data. The problems are motivated by applications in computer-aided design and manufacturing, medicine, biology, and spatial databases. A topic of current interest is efficient algorithms for efficient query processing on so called top-k query retrieval problems.