# Questions tagged [space-partitioning]

The tag has no usage guidance.

24 questions
Filter by
Sorted by
Tagged with
1 vote
23 views

### Clustering 2D points with flavour

Problem Description I have two sets of 2D points with flavours: Noisy points $$p_i = (x_i, y_i, f_i) : p_i \in N : |N|\approx 10^8$$ and true points p_{t_i} = (x_{t_i}, y_{t_i}, f_{t_i}) : p_{t_i} \...
1 vote
42 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 ...
395 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
27 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
99 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 ...
1 vote
279 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,...
103 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 ...
76 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
842 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
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
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 ...
1 vote
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 ...
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 ...
• 431
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
207 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
246 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 ...
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
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
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
123 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
180 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, ...
185 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
407 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
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'...