Approximate range searching: The absolute model

DOI10.1016/j.comgeo.2008.09.009zbMath1208.65031MaRDI QIDQ2269144

David M. Mount, Guilherme Dias 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

semigroups; approximation; convex bodies; range searching; idempotence; simplices; idempotent semigroups; halfspaces; range emptiness; absolute model; axis-aligned rectangles; Euclidean balls; halfbox quadtree

Mathematics Subject Classification ID

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

Related Items

Simplex Range Searching and Its Variants: A Review, Unnamed Item, FITTING FLATS TO POINTS WITH OUTLIERS, Tight lower bounds for halfspace range searching, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How hard is half-space range searching?
• Range searching with efficient hierarchical cuttings
• Range counting over multidimensional data streams
• The effect of corners on the complexity of approximate range searching
• Reporting points in halfspaces
• Approximate range searching
• Approximate range searching in higher dimension
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• On the importance of idempotence
• Lower Bounds on the Complexity of Polytope Range Searching
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• On approximate halfspace range counting and relative epsilon-approximations
• Approximate Range Searching: The Absolute Model
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Range Searching and Point Location among Fat Objects
• Efficiency of a Good But Not Linear Set Union Algorithm
• On approximate range counting and depth