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

DOI10.1137/S0097539798349188MaRDI QIDQ4507364zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(28)

• Optimal halfspace range reporting in three dimensions
• 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
• 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
• Centroid triangulations from \(k\)-sets
• 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
• Computing closest and farthest points for a query segment
• The edge labeling of higher order Voronoi diagrams
• The \(k\)-nearest-neighbor Voronoi diagram revisited
• Computing hereditary convex structures
• Cache-oblivious range reporting with optimal queries requires superlinear space
• Relative (p, )-approximations in geometry
• Constructing minimum-interference networks
• Range minima queries with respect to a random permutation, and approximate range counting
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• Dynamic data structures for \(k\)-nearest neighbor queries
• 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

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)