## Abstract

Recently, Arya, da Fonseca, and Mount [STOC 2011, SODA 2012] made notable progress in improving the ε- dependencies in the space/query-time tradeoffs for (1 + ε)-factor approximate nearest neighbor search in fixeddimensional Euclidean spaces. However, ε-dependencies in the preprocessing time were not considered, and so their data structures cannot be used to derive faster algorithms for offline proximity problems. Known algorithms for many such problems, including approximate bichromatic closest pair (BCP) and approximate Euclidean minimum spanning trees (EMST), typically have factors near (1/ε)^{d/2±O(1)} in the running time when the dimension d is a constant. We describe a technique that breaks the (1/ε)^{d/2} barrier and yields new results for many well-known proximity problems, including: an O((1/ε)^{d/3+O(1)}n)-time randomized algorithm for approximate BCP, an O((1/ε)^{d/3+O(1)}n log n)-time algorithm for approximate EMST, and an O(n log n + (1/ε)^{d/3+O(1)}n)-time algorithm to answer n approximate nearest neighbor queries on n points. Using additional bit-packing tricks, we can shave off the log n factor for EMST, and even move most of the "-factors to a sublinear term. The improvement arises from a new time bound for exact "discrete Voronoi diagrams", which were previously used in the construction of ε-kernels (or extent-based coresets), a well-known tool for another class of fundamental problems. This connection leads to more results, including: a streaming algorithm to maintain an approximate diameter in O((1/ε)^{d/3+O(1)}) time per point using O((1/ε)^{d/2+O(1)}) space, and a streaming algorithm to maintain an ε;- kernel in O((1/ε)^{d/4+O(1)}) time per point using O((1/ε)^{d=2+O(1)}) space. Copyright is held by the owner/author(s).

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

Title of host publication | Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014 |

Publisher | Association for Computing Machinery |

Pages | 416-425 |

Number of pages | 10 |

ISBN (Print) | 9781450325943 |

DOIs | |

State | Published - 2014 |

Externally published | Yes |

Event | 30th Annual Symposium on Computational Geometry, SoCG 2014 - Kyoto, Japan Duration: Jun 8 2014 → Jun 11 2014 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | 30th Annual Symposium on Computational Geometry, SoCG 2014 |
---|---|

Country/Territory | Japan |

City | Kyoto |

Period | 6/8/14 → 6/11/14 |

## Keywords

- Bichromatic closest pair
- Coresets
- Minimum spanning tree
- Nearest neighbor
- ε-dependencies

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics