A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model

DOI10.1007/s00454-018-0043-8zbMath1415.52017OpenAlexW2896673007WikidataQ129085716 ScholiaQ129085716MaRDI QIDQ2415377

Esther Ezra, Micha Sharir

Publication date: 21 May 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-018-0043-8

zbMATH Keywords

arrangement of hyperplanesepsilon-cuttings\(k\)-SUM and \(k\)-LDTlinear decision tree modelpoint location in geometric arrangementsvertical decomposition of geometric arrangements

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Combinatorial complexity of geometric structures (52C45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (6)

Geometric pattern matching reduces to \(k\)-SUM ⋮ Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location ⋮ Geometric Pattern Matching Reduces to k-SUM. ⋮ Active-learning a convex body in low dimensions ⋮ Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model ⋮ On 3SUM-hard problems in the decision tree model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved subquadratic 3SUM
• Point location in arrangements of hyperplanes
• Sharp bounds for vertical decompositions of linear arrangements in four dimensions
• A deterministic view of random sampling and its use in geometry
• \(\epsilon\)-nets and simplex range queries
• Cutting hyperplane arrangements
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• On the complexity of computations under varying sets of primitives
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Vertical decomposition of arrangements of hyperplanes in four dimensions
• On a class of \(O(n^ 2)\) problems in computational geometry
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• A note on point location in arrangements of hyperplanes
• Clustered Integer 3SUM via Additive Combinatorics
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Threesomes, Degenerates, and Love Triangles
• A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM
• Solving k-SUM using few linear queries
• Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
• Near-optimal linear decision trees for k-SUM and related problems
• Lower bounds for linear degeneracy testing

This page was built for publication: A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model