Point location among hyperplanes and unidirectional ray-shooting (Q1330461): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 13:48, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Point location among hyperplanes and unidirectional ray-shooting |
scientific article |
Statements
Point location among hyperplanes and unidirectional ray-shooting (English)
0 references
30 June 1995
0 references
An algorithm for locating a query point in an arrangement of hyperplanes in \(d\)-dimensional space is presented. Besides having better space complexity it differs from previously known algorithms also in that if a direction is chosen ahead of time, then the first hyperplane hit by shooting the query point in that direction can be found at no extra cost. Techniques used to obtain such result include probabilistic form of divide-and-conquer and its derandomization. By bootstrapping and mixing four intermediate solutions the final one is obtained.
0 references
point location
0 references
ray-shooting
0 references
query point
0 references