Questions tagged [space-partitioning]

The tag has no usage guidance.

5 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
72 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 ...
3
votes
0answers
163 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, ...
1
vote
0answers
13 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 ...
1
vote
0answers
15 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 ...
1
vote
0answers
35 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, ...