Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neibors in Any Minkowski Metric
Author
Mikhail J. Atallah, Marino Blanton, Michael T. Goodrich, and Stanislas Polu
Tech report number
CERIAS TR 2007-54
Abstract
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.
Series
Workshop on Algorithms and Data Structures (WADS'07)
Affiliation
Purdue University, University of California Irvine, Ecole Polytechnique
Publication Date
2007-08-01
Contents
1. Introduction
2. Discrepancy-Sensitive Dynamic Fractional Cascading
3. Dynamic Dominated Maxima
4. Dynamic Nearest Neighbors in Minkowski Metrics
5. Experimental Results
Subject
Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric
