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

DOI10.1137/S0097539798349188zbMATH Open0963.68207OpenAlexW2160775966MaRDI QIDQ4507364FDOQ4507364

Authors: 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

Recommendations

• Optimal halfspace range reporting in three dimensions
• Dynamic half-space range reporting and its applications
• Applications of random sampling in computational geometry. II
• Reporting points in halfspaces
• Approximating the \(k\)-level in three-dimensional plane arrangements

zbMATH Keywords

computational geometryrandomized algorithmsrange searchingVoronoi diagramsnearest neighbor searchinglevels in arrangementsrandomized data structures

Mathematics Subject Classification ID

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

Cited In (28)

• Independent range sampling, revisited
• The higher-order Voronoi diagram of line segments
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• Dynamic half-space range reporting and its applications
• Minimizing the error of linear separators on linearly inseparable data
• Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
• Centroid triangulations from \(k\)-sets
• Optimal deterministic shallow cuttings for 3-d dominance ranges
• Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Applications of random sampling in computational geometry. II
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• The edge labeling of higher order Voronoi diagrams
• Computing closest and farthest points for a query segment
• The \(k\)-nearest-neighbor Voronoi diagram revisited
• Computing hereditary convex structures
• Cache-oblivious range reporting with optimal queries requires superlinear space
• Relative \((p,\varepsilon )\)-approximations in geometry
• Constructing minimum-interference networks
• Range minima queries with respect to a random permutation, and approximate range counting
• Dynamic data structures for \(k\)-nearest neighbor queries
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• On approximate range counting and depth
• Simplex Range Searching and Its Variants: A Review
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Approximating the k-Level in Three-Dimensional Plane Arrangements
• Optimal halfspace range reporting in three dimensions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4507364)