2009/08/27 by Micha Sharir, Sharir, Micha, Hayim Shaul +1
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Machine Learning and Algorithms #Robotics and Sensor-Based Localization #cs.CG
paper · pdf · doi:10.48550/arxiv.0908.4061
openalex publication_date 2009/08/27 · arxiv created 2009/08/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a typical range emptiness searching (resp., reporting) problem, we are given a set P of n points in \realsd, and wish to preprocess it into a data structure that supports efficient range emptiness (resp., reporting) queries, in which we specify a range σ, which, in general, is a semi-algebraic set in \realsd of constant description complexity, and wish to determine whether P∩σ=∅, or to report all the points in P∩σ. Range emptiness searching and reporting arise in many applications, and have been treated by Matoušek \citeMa:rph in the special case where the ranges are halfspaces bounded by hyperplanes. As shown in \citeMa:rph, the two problems are closely related, and have solutions (for the case of halfspaces) with similar performance bounds. In this paper we extend the analysis to general semi-algebraic ranges, and show how to adapt Matoušek's technique, without the need to \em linearize the ranges into a higher-dimensional space. This yields more efficient solutions to several useful problems, and we demonstrate the new technique in four applications.