Approximate range searching: The absolute model

DOI10.1016/J.COMGEO.2008.09.009MaRDI QIDQ2269144zbMATH OpenOpenAlexFDO

Authors David M. Mount, Guilherme D. Da Fonseca

Publication date 16 March 2010

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1903/7037

zbMATH Keywords

absolute modelapproximationaxis-aligned rectanglesconvex bodiesEuclidean ballshalfbox quadtreehalfspacesidempotenceidempotent semigroupsrange emptinessrange searchingsemigroupssimplices

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The problem of range searching of a given geometric region \(R\) is considered in the scope of approximation with given approximation parameter \(\epsilon>0\). Unlike the existing approximation models, the new approach of the absolute model is applied. A variety of range spaces is are considered: halfspaces, Euclidean balls, simplices, axis-aligned rectangles, and general convex bodies. Also, different problem formulations are used: range searching under general commutative semigroups, idempotent semigroups, groups, and range emptiness.

Recommendations

• Approximate Range Searching: The Absolute Model
• Approximate range searching
• The effect of corners on the complexity of approximate range searching
• Approximate range searching in higher dimension
• scientific article; zbMATH DE number 1241835

Cites work

• Approximate range searching
• Approximate range searching in higher dimension
• Approximate Range Searching: The Absolute Model
• Data streams: algorithms and applications.
• Efficiency of a Good But Not Linear Set Union Algorithm
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• How hard is half-space range searching?
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• scientific article; zbMATH DE number 5019895 (Why is no real title available?)
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Lower Bounds on the Complexity of Polytope Range Searching
• On approximate halfspace range counting and relative epsilon-approximations
• On approximate range counting and depth
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• On the importance of idempotence
• Range counting over multidimensional data streams
• Range Searching and Point Location among Fat Objects
• Range searching with efficient hierarchical cuttings
• Reporting points in halfspaces
• Space-time tradeoffs for approximate spherical range counting
• The effect of corners on the complexity of approximate range searching

Cited in

(11)

• Approximate range searching
• On the importance of idempotence
• Approximate Range Searching: The Absolute Model
• Tight lower bounds for halfspace range searching
• Simplex Range Searching and Its Variants: A Review
• Output sensitive algorithms for approximate incidences and their applications
• Fitting flats to points with outliers
• Sublinear data structures for nearest neighbor in ultra high dimensions
• Output sensitive algorithms for approximate incidences and their applications
• Approximation algorithm for the kinetic robust \(k\)-center problem
• Enclosing weighted points with an almost-unit ball

This page was built for publication: Approximate range searching: The absolute model

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