Near-optimal Linear Decision Trees for k-SUM and Related Problems

DOI10.1145/3285953zbMath1427.68060OpenAlexW2938252862MaRDI QIDQ5244388

Shay Moran, Daniel M. Kane, Shachar Lovett

Publication date: 21 November 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3285953

zbMATH Keywords

hyperplane arrangementlinear decision treecomparison queriesinference dimension

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Data structures (68P05)

Related Items (6)

Geometric pattern matching reduces to \(k\)-SUM ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Time and space efficient collinearity indexing ⋮ Geometric Pattern Matching Reduces to k-SUM. ⋮ Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model ⋮ Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems

This page was built for publication: Near-optimal Linear Decision Trees for k-SUM and Related Problems