
Research
Abstracts  2007 
Computational Geometry through the Information LensErik D. Demaine & Mihai PătraşcuOverviewWe 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 twodimensional 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 finiteprecision onedimensional 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 onedimensional 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 [1] and repeatedly since. Our ResultsWe have jumpstarted this direction of research with several recent papers:
DiscussionThere 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 reanalyze many “standard” ideas and techniques in geometry through a new, informationtheoretic lens. This view of geometry seems interesting in its own right, and the algorithmic puzzles it raises are very appealing. References:[1] Dan E. Willard. Applications of the fusion tree method to computational geometry and searching. In Proceedings of the 3rd Annual ACMSIAM symposium on Discrete Algorithms, pp. 286–295, Orlando, Florida, United States, 1992. [2] 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. [3] 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. [4] 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. [5] Timothy M. Chan and Mihai Pătraşcu. Voronoi diagrams in n ⋅ 2^{O(√lg lg n)} time. In Proceedings of the 39th ACM Symposium on Theory of Computing, San Diego, California, June 2007. To appear. [6] Ilya Baran, Erik D. Demaine, and Mihai Pătraşcu. Subquadratic algorithms for 3SUM. Algorithmica. To appear. 

