# Questions tagged [space-partitioning]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
31 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 ...
19 views

### Deleted Partition and backing up data on Windows [closed]

so in order to make partition to install Ubuntu I have deleted my whole partition on hard disk and I thought all my data was lost. Then I come around notion that my data should be there even if I ...
17 views

### How to identify a continuous shape and break it into minimum number of rectangles?

The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous ...
14 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 ...
504 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 ...
1k 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 ...
30 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 ...
67 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 ...
120 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 ...
2k 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 ...
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, ...
95 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 ...
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, ...
112 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 ...
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'...