2018/04/23 by Daniel M. Kane, Shachar Lovett, Kane, Daniel M +3 · 1 citation
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning and Algorithms #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1804.08237
openalex publication_date 2018/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let H be an arbitrary family of hyper-planes in d-dimensions. We show that the point-location problem for H can be solved by a linear decision tree that only uses a special type of queries called generalized comparison queries. These queries correspond to hyperplanes that can be written as a linear combination of two hyperplanes from H; in particular, if all hyperplanes in H are k-sparse then generalized comparisons are 2k-sparse. The depth of the obtained linear decision tree is polynomial in d and logarithmic in |H|, which is comparable to previous results in the literature that use general linear queries. This extends the study of comparison trees from a previous work by the authors [Kane et al., FOCS 2017]. The main benefit is that using generalized comparison queries allows to overcome limitations that apply for the more restricted type of comparison queries. Our analysis combines a seminal result of Forster regarding sets in isotropic position [Forster, JCSS 2002], the margin-based inference dimension analysis for comparison queries from [Kane et al., FOCS 2017], and compactness arguments.