## Abstract

We reexamine fundamental problems from computational geometry in theallword RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for offline point location, a two-dimensional analog of sorting where one needs to order points with respect to segments. This result implies, for example, that the Voronoi diagram of n points in the plane can be constructed in (randomized) time n 2^{O( lg lg n)}. Similar bounds hold for numerous other geometric problems, such as three-dimensional convex hulls, planar Euclidean minimum spanning trees, line segment intersection, and triangulation of non-simple polygons. In FOCS'06, we developed a data structure for online point location, which implied a bound of O(n (lg n)/(lg lg n) for Voronoi diagrams and the other problems. Our current bounds are dramatically better, and a convincing improvement over the classic O(n lg n) algorithms. As in the field of integer sorting, the main challenge is to find ways to manipulate information, while avoiding the online problem (in that case, predecessor search).

Original language | English (US) |
---|---|

Title of host publication | STOC'07 |

Subtitle of host publication | Proceedings of the 39th Annual ACM Symposium on Theory of Computing |

Pages | 31-39 |

Number of pages | 9 |

DOIs | |

State | Published - 2007 |

Externally published | Yes |

Event | STOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 11 2007 → Jun 13 2007 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | STOC'07: 39th Annual ACM Symposium on Theory of Computing |
---|---|

Country/Territory | United States |

City | San Diego, CA |

Period | 6/11/07 → 6/13/07 |

## Keywords

- Computational geometry
- Convex hulls
- Point location
- Segment intersection
- Sorting
- Word-RAM algorithms

## ASJC Scopus subject areas

- Software

## Fingerprint

Dive into the research topics of 'Voronoi diagrams in n 2^{o(√lg lg n)}time'. Together they form a unique fingerprint.