Tag Info

Hot answers tagged space-partitioning

11

I think you've misunderstood what the parity data is. They're not parity checks, so it's not true that "each parity block is specific to each disc it belongs to." The parity data is to allow recovery from a failed disc. Let's go back to RAID-4 for a second, and assume we have three discs: discs $0$ and  $1$ are data and disc $2$ is parity. "Parity"...

5

Use a 2-d segment tree. Assuming we have $n$ items, construction takes time $O(n \cdot \log^2(n))$ and each query takes $O(\log^2(n))$ time. These times become $O(n \cdot \log(n))$ and $O(\log(n))$ time, respectively, if we use fractional cascading and lowest-level interval tree. These are good times unless there is more problem structure. The query is ...

2

An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.

2

They're very similar, as you say. Their asymptotic running time is equivalent; the difference in running time and space usage is at most a small constant. However, in practice, constants can matter. In practice, the octree might perform better, due to its better memory locality. If the depth of the octree is $d$, the depth of your corresponding binary ...

2

The general problem is called Circle packing, which gets easier with equiradius circles, to get hexagonal grid and put circles on hexagon vertices and one in the center. This works on Euclidian space, so the hexagon coordinates should be converted by some kind of mapping, for example Vincenty formulae. This method will give really neglible overlapping, but ...

2

You could use a k-d tree. A k-d tree normally alternates between partitioning horizontally and partitioning vertically, but you could certainly modify it to change that pattern (e.g., partition horizontally twice in a row; or equivalently, partition horizontally into three or four regions rather than just into two regions). Not everything has a "name". ...

1

This is the clique cover problem in disguise, and finding an optimal solution NP-hard.

1

Here's a simple idea that I believe can generate all partitions. There are two types of subdivisions: Given a rectangle, randomly generate a horizontal or vertical line to partition it into two subrectangles. (The usual "split in two" rule.) Given a rectangle, randomly generate a rectangle that fits inside it. Consider the 4 corners of this inner ...

1

The Covertree is a specialized data structure for neighbour search. However I don't know it's update performance. A better option may be the PH-Tree (my own implementation). It is similar to a quadtree, but implemented as a prefix-sharing bit-level trie. Advantages: Maximum depth of the tree is 64 (assuming 64bit per dimension) No reordering, ever. This ...

1

Solution outline: We will maintain two AVL trees. Tree_X: will hold points sorted by their X coordinate. Tree_Y: will hold points sorted by their Y coordinate. Each node within both trees will hold the following additional data: Number of leaves in left sub-tree. Number of leaves in right sub-tree. For a point $(x,y)$ we will define regions $A$ ,$B$, $C$...

Only top voted, non community-wiki answers of a minimum length are eligible