2026-08-10T22:48:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9086 2024-03-06T10:43:20Z ddc:004 open_access

Generalized Comparison Trees for Point-Location Problems Kane, Daniel M. Lovett, Shachar Moran, Shay linear decision trees comparison queries point location problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel M. Kane and Shachar Lovett and Shay Moran 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.82 urn:nbn:de:0030-drops-90862 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.82 eng https://creativecommons.org/licenses/by/3.0/legalcode