Concepedia

Halfspace Range Searching

Halfspace Range Searching is a range searching paradigm in computational geometry where the query region is defined by a halfspace, distinguishing it from other range searching methods by its use of linear inequalities to partition the space and retrieve points lying on one side of a hyperplane.

24

Publications

974

Citations

29

Authors

25

Institutions

Publications per year

2017–2026

0

Parents

Publications

24

Epsilon-nets and simplex range queries

David Haussler, Emo Welzl · 1986 · 142 citations · Full text

, , +14

Secure and efficient range queries on outsourced databases using Rp-trees

Peng Wang, Chinya V. Ravishankar · 2013 · 123 citations

, , +17

Halfplanar range search in linear space and O(n0.695) query time

Herbert Edelsbrunner, Emo Welzl · Information Processing Letters · 1986 · 94 citations

, , +12

Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions

Timothy M. Chan · SIAM Journal on Computing · 2000 · 89 citations

, , +16

Optimal halfspace range reporting in three dimensions

Peyman Afshani, Timothy M. Chan · 2009 · 68 citations

, , +11

1–5 of 24

Authors

29

  1. TM
    Timothy M. Chan

    University of Waterloo, Canada

    6 publications · 231 citations

    6

    h-index

  2. BC
    Bernard Chazelle

    Princeton University, United States

    4 publications · 155 citations

    4

    h-index

  3. PG
    Prosenjit Gupta

    University of Minnesota, United States

    2 publications · 36 citations

    2

    h-index

  4. HB
    Hervé Brönnimann

    New York University, United States

    2 publications · 68 citations

    2

    h-index

  5. PA
    Peyman Afshani

    Aarhus University, Denmark

    2 publications · 92 citations

    2

    h-index

1–5 of 29

Institutions

25

  1. University of Waterloo

    Waterloo, Canada

    4 h-index

    6 publications

    224 citations

  2. Princeton University

    Princeton, United States

    3 h-index

    4 publications

    150 citations

  3. Hong Kong University of Science and Technology

    Hong Kong, Hong Kong

    3 h-index

    5 publications

    60 citations

  4. Max Planck Society

    Munich, Germany

    2 h-index

    3 publications

    58 citations

  5. University of Maryland, College Park

    College Park, United States

    2 h-index

    2 publications

    25 citations

  6. Graz University of Technology

    Graz, Austria

    2 h-index

    3 publications

    330 citations

  7. Aarhus University

    Aarhus, Denmark

    2 h-index

    2 publications

    39 citations

  8. University of Illinois System

    Urbana, United States

    1 h-index

    1 publications

    43 citations

1–8 of 25

Venues

  1. SIAM Journal on Computing

    6 publications · 222 citations

    6

    h-index

  2. Discrete & Computational Geometry

    4 publications · 144 citations

    4

    h-index

  3. Information Processing Letters

    1 publications · 94 citations

    1

    h-index

  4. Computational Geometry

    1 publications · 22 citations

    1

    h-index

  5. Symposium on Discrete Algorithms

    Conference · 1 publications · 12 citations

    1

    h-index

1–5