Practical low-dimensional halfspace range space sampling

DOI10.4230/LIPICS.ESA.2018.62MaRDI QIDQ5009629zbMATH OpenFDO

Authors Michael Matheny, Jeff M. Phillips

Publication date 4 August 2021

Full work available at URL https://arxiv.org/abs/1804.11307

zbMATH Keywords

halfspacespartitionsrange spacessampling

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Approximate halfspace range counting
• On approximate halfspace range counting and relative epsilon-approximations
• Reporting points in halfspaces
• Optimal private halfspace counting via discrepancy
• Computing approximate statistical discrepancy

Cites work

• A deterministic view of random sampling and its use in geometry
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• A spatial scan statistic
• Algorithms for ham-sandwich cuts
• Constructing Planar Cuttings in Theory and Practice
• Constructive discrepancy minimization by walking on the edges
• Deterministic sampling and range counting in geometric data streams
• Efficient partition trees
• Geometric discrepancy. An illustrated guide
• Geometric methods in the study of irregularities of distribution
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• Improved bounds on the sample complexity of learning
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Optimal partition trees
• Partitioning with two lines in the plane
• Polygon Retrieval
• Range counting over multidimensional data streams
• Tight upper bounds for the discrepancy of half-spaces
• Weighted random sampling with a reservoir

Cited in

(4)

• Computing approximate statistical discrepancy
• Computing optimal \(\varepsilon\)-nets is as easy as finding an unhit set
• An optimal sparsification lemma for low-crossing matchings and its applications to discrepancy and approximations
• Escaping the curse of spatial partitioning: matchings with low crossing numbers and their applications

Describes a project that uses

Uses Software

• 2D Arrangement
• CGAL

This page was built for publication: Practical low-dimensional halfspace range space sampling

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