Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges. / Afshani, Peyman; Tsakalidis, Konstantinos.

In: Algorithmica, Vol. 80, No. 11, 11.2018, p. 3192-3206.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

APA

CBE

MLA

Vancouver

Author

Afshani, Peyman ; Tsakalidis, Konstantinos. / Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges. In: Algorithmica. 2018 ; Vol. 80, No. 11. pp. 3192-3206.

Bibtex

@article{69023aa646b143c8a775cf975efa84b5,
title = "Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges",
abstract = "Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n three-dimensional points, construct optimal-size (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in (Formula presented.) worst-case time, using (Formula presented.) space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraic-comparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomial-time guarantees by Matou{\v s}ek (Comput Geom 2(3):169–186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912–953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3-d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866–881, 2016). Our methods yield worst-case efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the word-RAM models, where such shallow cuttings are utilized to support queries efficiently.",
keywords = "Computational geometry, Orthogonal range searching, Shallow cuttings",
author = "Peyman Afshani and Konstantinos Tsakalidis",
year = "2018",
month = nov,
doi = "10.1007/s00453-017-0376-3",
language = "English",
volume = "80",
pages = "3192--3206",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York LLC",
number = "11",

}

RIS

TY - JOUR

T1 - Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges

AU - Afshani, Peyman

AU - Tsakalidis, Konstantinos

PY - 2018/11

Y1 - 2018/11

N2 - Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n three-dimensional points, construct optimal-size (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in (Formula presented.) worst-case time, using (Formula presented.) space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraic-comparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomial-time guarantees by Matoušek (Comput Geom 2(3):169–186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912–953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3-d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866–881, 2016). Our methods yield worst-case efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the word-RAM models, where such shallow cuttings are utilized to support queries efficiently.

AB - Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n three-dimensional points, construct optimal-size (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in (Formula presented.) worst-case time, using (Formula presented.) space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraic-comparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomial-time guarantees by Matoušek (Comput Geom 2(3):169–186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912–953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3-d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866–881, 2016). Our methods yield worst-case efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the word-RAM models, where such shallow cuttings are utilized to support queries efficiently.

KW - Computational geometry

KW - Orthogonal range searching

KW - Shallow cuttings

UR - http://www.scopus.com/inward/record.url?scp=85029574246&partnerID=8YFLogxK

U2 - 10.1007/s00453-017-0376-3

DO - 10.1007/s00453-017-0376-3

M3 - Journal article

AN - SCOPUS:85029574246

VL - 80

SP - 3192

EP - 3206

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 11

ER -