Point location among hyperplanes and unidirectional ray-shooting (Q1330461): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: A deterministic view of random sampling and its use in geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New applications of random sampling in computational geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Randomized Algorithm for Closest-Point Queries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Applications of random sampling in computational geometry. II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3772828 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: \(\epsilon\)-nets and simplex range queries / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cutting hyperplane arrangements / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal randomized parallel algorithms for computational geometry / rank | |||
Normal rank |
Latest revision as of 16:57, 22 May 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