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

Simple item page
dc.creatorAtallah, Mikhail J.
dc.creatorBlanton, Marina
dc.creatorGoodrich, Michael T.
dc.creatorPolu, Stanislas
dc.date2009-04-29
dc.date.accessioned2026-07-07T13:09:59Z
dc.date.available2026-07-07T13:09:59Z
dc.descriptionThis 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.
dc.descriptionExpanded version of a paper that appeared in WADS 2007
dc.identifierhttps://arxiv.org/abs/0904.4670
dc.identifierhttp://arxiv.org/abs/0904.4670
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/228922
dc.subjectData Structures and Algorithms
dc.subjectComputational Geometry
dc.titleDiscrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric
dc.typetext

Files

Collections

arXiv