Abstract:

Range searching is a classical problem that has been studied extensively both in computational geometry and databases. Over the last three decades, several sophisticated geometric techniques and data structures (e.g. kd-trees, range trees, eps-nets, cuttings, simplicial partitions) have been proposed for range searching that have had a profound impact on the field, much beyond range searching. Despite this tremendous progress on range searching, there is a big gap between theoretical results and the approaches used in practice for this problem, partly because the theoretically best known results are not easy to implement and partly because the goals have shifted. This talk begins by reviewing some of the theoretical results, and then focuses on new variants of range searching that have emerged in the last few years and discusses some of the approaches that are being used in practice.

Bio sketch:

Dr. Agarwal earned his PhD in Computer Science from the Courant Institute of Mathematical Sciences at New York University.  He joined Duke University in 1989 where he is now the RJR Nabisco Professor of Computer Science and a Professor of Mathematics. He was the Chair of the Department of Computer Science from 2004 to 2010.  His research interests include geometric computing, spatial databases, ecological modeling, geographic information systems, sensor networks, computational molecular biology, and robotics.  A Sloan Fellow, an ACM Fellow, and a National Young Investigator, Dr. Agarwal has authored four books and more than three hundred research articles. He serves on the editorial boards of a number of journals and on the advisory boards of several institutes and centers.

Host: Professor Lars Arge