Questions tagged [space-partitioning]
The space-partitioning tag has no usage guidance.
23
questions
1
vote
1
answer
36
views
Detecting non-airtight geometry
I have a finite region of 3D space that some (arbitrarily-shaped, concave) geometry occupies, and I need to identify whether that geometry forms a closed 3D volume (or multiple disjoint closed 3D ...
2
votes
0
answers
302
views
Data Structure for finding all bounding boxes that overlap or are contained in a given bounding box
I am looking for a data structure that needs to have very fast and accurate queries to solve the following:
The input:
A set of 3 Dimensional axis-aligned bounding boxes B
A separate 3D axis aligned ...
- 21
0
votes
0
answers
23
views
Efficient way of partitionning a set into a fixed number of parts
I am looking for a way of efficiently partitionning a set of consecutive integers in to a set where the number $K$ of parts is given.
For instance, for the set {1, 2, 3, 4}, I would like the best way ...
- 465
0
votes
0
answers
98
views
Find a bipartition of points using blackbox
Suppose given $n$ pair of points $P=\{(p_1,q_1),\dots,(p_n,q_n)\}$ in the plane that each pair $(p_i,q_i)\in \mathbb{R}^2$ can't belong to the same group. We want to partition points into $K$ groups ...
user146750
1
vote
1
answer
235
views
Nearest neighbor search in latitude/longitude coordinates
I have two sets of lat/long points, $A$ and $B$. For each point $a$ in $A$, I want to find the corresponding closest point (by Haversine distance) $b$ in $B$. I'd like to use a space-partitioning tree,...
- 11
6
votes
1
answer
100
views
Closest point in embedded simplicial complex
Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded ...
- 161
3
votes
0
answers
71
views
Algorithm to cut a sphere in half with a plane and maximize the number of points on the sphere surface on one side of the plane
Consider a sphere with a coordinate system like the earth. There are $N$ points on its surface at random positions. For all the infinite planes that cuts the sphere exactly in half (i.e. the sphere's ...
- 131
0
votes
1
answer
749
views
Find nearest neighbour in a radius
I have a set of points A in my space (geo points but I can assume they are on a 2D plane).
I have another set of points B.
For every point in B I want to find every point in A inside a radius R with ...
- 13
1
vote
0
answers
18
views
Data Structure for high dimensional data with nullable coordinates
Are there alternatives to uniform grid spatial partitioning when considering data structures for data with nullable or missing coordinate values?
For example with uniform grid spatial partitioning ...
- 11
1
vote
2
answers
93
views
Sequential subsequence removal with arbitrary predicate
I want to extract sub-sequences from a sequence of float values.
The "scale" and range of these values is arbitrary (as I can manipulate it at will) but the "shape" is consistent.
For a visual ...
- 11
1
vote
0
answers
18
views
Balanced $\epsilon$-separated partitioning by a hyperplane
Suppose we have $m$ points in $R^n$ and $\epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $\epsilon$-close to it is minimum, with the constraint that ...
- 531
5
votes
1
answer
2k
views
Why does RAID-5 require an additional disk for parity blocks?
I know that RAID-5 consists of block-level striping across multiple disks, but using an additional parity-check block on each disk .. and that at least two disks are required for striping.
And it's ...
- 421
0
votes
2
answers
58
views
Packing objects into bins to minimize the number of bins
There is a list of objects. Each object cannot be in a bin with some other objects. How can I find the minimum number of bins required to hold all the objects (and the objects in them)?
My current ...
- 103
4
votes
0
answers
190
views
Arrange objects in space so that the outline takes the least surface/volume
Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible.
On the below image ...
- 209
2
votes
2
answers
239
views
Tree structure that is like a quadtree/octree but splits a different number of times in each dimension?
I'm looking for a data structure that is like a quadtree where each level is a subdivision of the previous. However, unlike a quadtree I need the subdivision to occur a different number of times in ...
- 123
6
votes
2
answers
5k
views
Randomly partition an rectangle into N smaller rectangles
I'm looking for an algorithm that can partition a rectangle into N smaller rectangles, at random. N will be small (on the order of 5-10 in most cases). It need not be uniformly at random, but at the ...
- 162
5
votes
1
answer
1k
views
Query all bounding boxes which contain a point
I'm looking for the most efficient spatial-indexing data-structure for storing and querying bounding boxes which contain individual points. The points represent 2D coordinates on a grid, while the ...
- 153
1
vote
0
answers
39
views
balanced partitioning of nonconvex area between multiple agents in a grid world
In the original art gallery problem, there is a non-convex area provided and one has to divide it into regions based on infinite visibility of guards. We assume an unlimited number of guards. However, ...
- 163
3
votes
1
answer
110
views
Given a list of points on a sphere find the place for another point such that most space is covered?
Suppose I knew my current location as a geographical point (Lat/Lng) and had a standard radius to search (meters). Now given a list of previously searched geographical points as the centers of circles ...
- 131
3
votes
0
answers
179
views
Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points
I have a point cloud of N points in D-dimensional space with periodic boundary conditions, where N can range from 500 to 10^8 and D can range from 1 to 20. The distribution of points varies wildly, ...
- 31
7
votes
2
answers
181
views
A key-value datastructure with fast (on average) member move and nearest neighbors search?
I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
- 201
3
votes
1
answer
388
views
Represent an octree as a binary tree of thrice the depth?
In an octree, each node has up to eight child nodes. This can be implemented with eight pointers per node that are set to null pointers if the child is not used. Another implementation uses a byte as ...
- 143
4
votes
1
answer
304
views
Data structure to hold and retrieve points in a plane
Definition 1: Point $(x,y)$ is controlling point $(x',y')$ if and only if $x < x'$ and $y < y'$.
Definition 2: Point $(x,y)$ is controlled by point $(x',y')$ if and only if $x' < x $ and $ y'...
- 213