patternMinor
Fast algorithm to find points on one side of hyperplane?
Viewed 0 times
fastpointssidealgorithmonehyperplanefind
Problem
Given $n$ points $x_1, x_2, ..., x_n \in \mathbb{R}^k$, where $\mathbb{R}^k$ can be high dimensional. Is it possible to devise a fast algorithm
(1) Preparation: first take the n points as an input, do whatever preprocessing necessary.
(2) Query: for each query $f_i = w^\top x$ being a hyperplane and a constant $b$, find the subset of points $\{x_i | w^\top x_i \geq b\}$.
such that the asymptotic complexity for the query is less than $\Theta(k \cdot n)$ ?
(1) Preparation: first take the n points as an input, do whatever preprocessing necessary.
(2) Query: for each query $f_i = w^\top x$ being a hyperplane and a constant $b$, find the subset of points $\{x_i | w^\top x_i \geq b\}$.
such that the asymptotic complexity for the query is less than $\Theta(k \cdot n)$ ?
Solution
The keywords you may be looking for are simplex range searching and half-space range searching. See chapter 16 of Computational Geometry: Algorithms and Applications. If you are interested in general simplices (intersections of multiple half-planes), then there are two data structures in particular that might interest you: partition trees and cutting trees.
In the following paper describing partition trees, we have query time of $O(n^{1-1/d}(\log n)^{O(1)})$, preprocessing time of $O(n \log n)$, and space requirement of $O(n)$.
Matoušek, Jiří. "Efficient partition trees." Discrete & Computational Geometry 8.1 (1992): 315-334.
In a cutting tree, you consider the dual case (each point in your input is represented by a line in the dual plane) and you tradeoff space for query time. You get $O(\log n)$ query time at a cost of $O(n^{2+\epsilon})$ space.
However, if you really only care about a single half-plane in your query, you can do better. In The Power of Geometric Duality, Chazelle gives an optimal data structure for half-space range queries with $O(\log n + k)$ query time and $O(n)$ space.
In the following paper describing partition trees, we have query time of $O(n^{1-1/d}(\log n)^{O(1)})$, preprocessing time of $O(n \log n)$, and space requirement of $O(n)$.
Matoušek, Jiří. "Efficient partition trees." Discrete & Computational Geometry 8.1 (1992): 315-334.
In a cutting tree, you consider the dual case (each point in your input is represented by a line in the dual plane) and you tradeoff space for query time. You get $O(\log n)$ query time at a cost of $O(n^{2+\epsilon})$ space.
However, if you really only care about a single half-plane in your query, you can do better. In The Power of Geometric Duality, Chazelle gives an optimal data structure for half-space range queries with $O(\log n + k)$ query time and $O(n)$ space.
Context
StackExchange Computer Science Q#23961, answer score: 4
Revisions (0)
No revisions yet.