Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric

Mikhail J. Atallah; Marina Blanton; Michael T. Goodrich; Stanislas Polu

doi:10.1007/978-3-540-73951-7_11

Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric

Mikhail J. Atallah
, Marina Blanton
, Michael T. Goodrich
, Stanislas Polu

Department of Computer Science and Engineering

Purdue University
University of California at Irvine
École Polytechnique

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

Original language	English
Title of host publication	Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings
Publisher	Springer Verlag
Pages	114-126
Number of pages	13
ISBN (Print)	3540739483, 9783540739487
DOIs	https://doi.org/10.1007/978-3-540-73951-7_11
State	Published - 2007
Event	10th International Workshop on Algorithms and Data Structures, WADS 2007 - Halifax, Canada Duration: Aug 15 2007 → Aug 17 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4619 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Workshop on Algorithms and Data Structures, WADS 2007
Country/Territory	Canada
City	Halifax
Period	08/15/07 → 08/17/07

Access to Document

10.1007/978-3-540-73951-7_11

Cite this

Atallah, M. J., Blanton, M., Goodrich, M. T., & Polu, S. (2007). Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric. In Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings (pp. 114-126). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4619 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73951-7_11

Atallah, Mikhail J. ; Blanton, Marina ; Goodrich, Michael T. et al. / Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric. Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag, 2007. pp. 114-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{891372a60cfc4b3395bc632367665ff9,

title = "Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric",

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.",

author = "Atallah, \{Mikhail J.\} and Marina Blanton and Goodrich, \{Michael T.\} and Stanislas Polu",

year = "2007",

doi = "10.1007/978-3-540-73951-7\_11",

language = "English",

isbn = "3540739483",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "114--126",

booktitle = "Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings",

address = "Germany",

note = "10th International Workshop on Algorithms and Data Structures, WADS 2007 ; Conference date: 15-08-2007 Through 17-08-2007",

}

Atallah, MJ, Blanton, M, Goodrich, MT & Polu, S 2007, Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric. in Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4619 LNCS, Springer Verlag, pp. 114-126, 10th International Workshop on Algorithms and Data Structures, WADS 2007, Halifax, Canada, 08/15/07. https://doi.org/10.1007/978-3-540-73951-7_11

Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric. / Atallah, Mikhail J.; Blanton, Marina; Goodrich, Michael T. et al.
Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag, 2007. p. 114-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4619 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric

AU - Atallah, Mikhail J.

AU - Blanton, Marina

AU - Goodrich, Michael T.

AU - Polu, Stanislas

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/38149007180

U2 - 10.1007/978-3-540-73951-7_11

DO - 10.1007/978-3-540-73951-7_11

M3 - Conference contribution

AN - SCOPUS:38149007180

SN - 3540739483

SN - 9783540739487

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 114

EP - 126

BT - Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings

PB - Springer Verlag

T2 - 10th International Workshop on Algorithms and Data Structures, WADS 2007

Y2 - 15 August 2007 through 17 August 2007

ER -

Atallah MJ, Blanton M, Goodrich MT, Polu S. Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric. In Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag. 2007. p. 114-126. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73951-7_11

Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any minkowski metric

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this