Questions tagged [space-partitioning]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
26 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,...
6
votes
1answer
65 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 ...
3
votes
0answers
41 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 ...
0
votes
1answer
57 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 ...
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
2answers
71 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
0answers
16 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 ...
5
votes
1answer
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 ...
0
votes
2answers
44 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 ...
4
votes
0answers
73 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 ...
2
votes
2answers
149 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 ...
6
votes
2answers
3k 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 ...
4
votes
1answer
694 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 ...
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, ...
3
votes
1answer
96 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 ...
3
votes
0answers
164 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, ...
7
votes
2answers
137 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 ...
3
votes
1answer
277 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 ...
3
votes
1answer
181 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'...