# Tag Info

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

The K-D tree is a good data structure for solving this. However you can't blindly apply the search procedure only to the center point, you must be a bit smarter. While searching the K-D tree for your points, every time you must choose the left or right child to search in, check whether the splitting plane is to the left of your circle, intersects it, or is ...

1

Use changepoint detection. This will identify the boundaries between the clusters.

1

Set threshold to, say 30 (arbitrary value greater than noise in the plot) and start from left to right, if value is greater than threshold, keep it as run - collect data to temporary array, if values drop below threshold then discard data and create new array for another run. This will cut 5 bars and discard data between, if you want to keep data, you have ...

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