### Abstract

We study the problem of Nearest-Neighbor Searching under locational uncertainty. Here, an uncertain query or site consists of a set of points in the plane, and their distance is defined as distance between the two farthest points within them. In L_{∞} metric, we present an algorithm with O(nlog^{2} n+s) expected preprocessing time, O(nlog n) space, and O(log^{2} n + k) query time, where s is the total number of site points, n is the number of sites, and k is the size of the query. We also propose a √2-approximation algorithm for the L_{2} version of the problem.

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

Pages | 89-94 |

Number of pages | 6 |

State | Published - Jan 1 2017 |

Event | 29th Canadian Conference on Computational Geometry, CCCG 2017 - Ottawa, Canada Duration: Jul 26 2017 → Jul 28 2017 |

### Conference

Conference | 29th Canadian Conference on Computational Geometry, CCCG 2017 |
---|---|

Country | Canada |

City | Ottawa |

Period | 7/26/17 → 7/28/17 |

### ASJC Scopus subject areas

- Computational Mathematics
- Geometry and Topology

## Fingerprint Dive into the research topics of 'Nearest-neighbor search under uncertainty'. Together they form a unique fingerprint.

## Cite this

Aronov, B., Iacono, J., & Sheikhan, K. (2017).

*Nearest-neighbor search under uncertainty*. 89-94. Paper presented at 29th Canadian Conference on Computational Geometry, CCCG 2017, Ottawa, Canada.