Abstracts - 2007
Computational Geometry through the Information Lens
Erik D. Demaine & Mihai Pătraşcu
We are revisiting classic problems in computational geometry from the modern algorithmic perspective of exploiting the bounded precision of the input. In one dimension, this viewpoint has taken over as the standard model of computation, and has led to a powerful suite of techniques for both upper and lower bounds that constitute a mature field of research. But the same tools simply do not apply to two and higher dimensions, aside from orthogonal problems. For example, it is tempting to wonder whether the simple idea of radix sort can be extended to improve the running time of a simple two-dimensional problem like constructing a Voronoi diagram, but this problem has remained uncracked for many years despite extensive effort.
We aim to fill this gap between computational geometry, which generally assumes infinite precision inputs and computation, and most of the rest of theoretical computer science. This gap has become increasingly apparent as techniques for finite-precision one-dimensional problems have been improved and developed. For this reason, several researchers have exploited finite precision in orthogonal problems in higher dimensions, where essentially the same one-dimensional ideas apply, but have so far been unsuccessful in extending these results to nonorthogonal problems. This shortcoming for nonorthogonal problems was highlighted 15 years ago by Willard  and repeatedly since.
We have jump-started this direction of research with several recent papers:
There is a close relation between this direction of research and engineering practice. Geometric computer programs already exploit the fixed precision of the input, and our work can be seen as a justification for some of these “heuristics”. Our goal is to understand the extent to which fixed precision can be exploited and to develop new, more practical techniques for solving classic geometric problems.
Our work so far has forced us to re-analyze many “standard” ideas and techniques in geometry through a new, information-theoretic lens. This view of geometry seems interesting in its own right, and the algorithmic puzzles it raises are very appealing.
 Dan E. Willard. Applications of the fusion tree method to computational geometry and searching. In Proceedings of the 3rd Annual ACM-SIAM symposium on Discrete Algorithms, pp. 286–295, Orlando, Florida, United States, 1992.
 Mihai Pătraşcu. Planar point location in sublogarithmic time. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 325–332, Berkeley, California, October 2006.
 Timothy M. Chan. Point location in o(log n) time, Voronoi diagrams in o(n log n) time, and other transdichotomous results in computational geometry. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 333–342, Berkeley, California, October 2006.
 Erik D. Demaine and Mihai Pătraşcu. Tight bounds for dynamic convex hull queries (again). In Proceedings of the 23rd Annual ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 2007. To appear.
 Timothy M. Chan and Mihai Pătraşcu. Voronoi diagrams in n ⋅ 2O(√lg lg n) time. In Proceedings of the 39th ACM Symposium on Theory of Computing, San Diego, California, June 2007. To appear.
 Ilya Baran, Erik D. Demaine, and Mihai Pătraşcu. Subquadratic algorithms for 3SUM. Algorithmica. To appear.