Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

This paper studies a discrepancy-sensitive approach to dynamic fractional cascading. We provide an efficient data structure for dominated maxima searching in a dynamic set of points in the plane, which in turn leads to an efficient dynamic data structure that can answer queries for nearest neighbors using any Minkowski metric. We provide an efficient data structure for dominated maxima searching in a dynamic set of points in the plane, which in turn leads to an efficient dynamic data structure that can answer queries for nearest neighbors using any Minkowski metric.
Expanded version of a paper that appeared in WADS 2007

Keywords

Data Structures and Algorithms, Computational Geometry

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/228922

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0904.4670
 http://arxiv.org/abs/0904.4670

Collections

arXiv