# 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 ...

3

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

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

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 ...

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

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

First things first, if this is really a geography problem, then you probably don't want to calculate distances on the sphere, but rather on the reference ellipsoid. But even then, the reference ellipsoid is close enough to a sphere that it works as an approximation, and then accurate distances can be computed as appropriate. You've already worked out that if ...

1

If you have only a single k-complex and you want to get the closest point regardless of whether it is a neighbor, then you can simply use any spatial index that supports nearest neighbor queries. For low dimensionality, such as 3 or 6, kd-trees, r-trees or some quadtrees (such as the PH-Tree) will work fine. In my experience, especially the R-Tree and PH-...

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

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