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

DOI10.1137/S0097539798349188zbMath0963.68207OpenAlexW2160775966MaRDI QIDQ4507364

Timothy M. Chan

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539798349188

zbMATH Keywords

computational geometryrandomized algorithmsVoronoi diagramsrange searchingnearest neighbor searchinglevels in arrangementsrandomized data structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Data structures (68P05)

Related Items (24)

Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment ⋮ A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams ⋮ A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams ⋮ An efficient randomized algorithm for higher-order abstract Voronoi diagrams ⋮ Dynamic data structures for \(k\)-nearest neighbor queries ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Constructing minimum-interference networks ⋮ CENTROID TRIANGULATIONS FROM k-SETS ⋮ On approximate range counting and depth ⋮ Optimal deterministic shallow cuttings for 3-d dominance ranges ⋮ Computing closest and farthest points for a query segment ⋮ Computing hereditary convex structures ⋮ Cache-oblivious range reporting with optimal queries requires superlinear space ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions ⋮ The \(k\)-nearest-neighbor Voronoi diagram revisited ⋮ The higher-order Voronoi diagram of line segments

This page was built for publication: Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions