Dynamic point location in arrangements of hyperplanes

DOI10.1007/BF02293052zbMath0752.68045OpenAlexW4254041727MaRDI QIDQ1199133

Sandeep Sen, Ketan D. Mulmuley

Publication date: 16 January 1993

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02293052

zbMATH Keywords

hyperplanespoint-locationmaintaining data structuresray-shooting queries

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (2)

Dynamic point location in arrangements of hyperplanes ⋮ RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS

Cites Work

• Unnamed Item
• A deterministic view of random sampling and its use in geometry
• The design of dynamic data structures
• \(\epsilon\)-nets and simplex range queries
• Parallel construction of subdivision hierarchies
• Euclidean minimum spanning trees and bichromatic closest pairs
• Optimal randomized parallel algorithms for computational geometry
• Dynamic point location in arrangements of hyperplanes
• Point location among hyperplanes and unidirectional ray-shooting
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• A randomized algorithm for fixed-dimensional linear programming
• A linear algorithm for determining the separation of convex polyhedra
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• Fully Dynamic Point Location in a Monotone Subdivision
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Dynamic point location in arrangements of hyperplanes