Constant Time Search

Question

Suppose I have a rod that I cut into pieces. Given a point on the source rod, is there a way to find out which part it belongs to in constant time?

For instance:

|------------------|---------|---------------| 0.0 4.5 7.8532 9.123 

Given the position:

  ^ | 8.005 

I would like to receive a 3rd piece .

You can easily get such an answer O (log n) times with binary search, but is it possible to do this in O (1)? Should I pre-process cut positions?

Answer 1

If you assume that the point you want to query is evenly randomly selected along the bar, then you can have the EXPECTED constant time without a crazy memory burst as follows. If you split a bar into N equally spaced parts, where N is the number of source irregularly spaced segments that you have on your rod, and then write for each of N equal sized shapes that overlap from the original irregular segment (s), then for To complete the query, you first simply take the query point and do a simple round off to find out which uniformly distributed part it is in, then use this index to see which of your source segments intersects equally spaced portion, and then check each intersecting source segment to see if the segment contains your point (and you can use binary search if you want to make sure that the worst performance is still logarithmic). The expected runtime for this approach is constant if you assume that the query point is randomly selected along your rod, and the memory size is O (N), if your rod was originally cut into N irregular shapes, so there are no crazy memory requirements.

PROOF OF EXPECTED O (1) OPERATION TIME:

When you count the total number of intersection pairs between your original N irregular segments and N equally distributed parts that I propose to build, the total number is no more than 2 * (N + 1) (because if you sort all the end points of all regular and irregular segments , a new pair of intersections can always be charged to one of the end points defining either a regular or an irregular segment). Thus, you have a multi-set of no more than 2 (N + 1) of your irregular segments, distributed differently among the N regular segments that they intersect. The actual distribution of intersections between regular segments does not matter. When you have a single query point and calculate the expected number of irregular segments that intersect the regular segment containing the query point, each regular segment has a 1 / N probability selected by the query point, so the expected number of intersecting irregular segments to be checked is 2 * (N + 1) / N = O (1).

Answer 2

For arbitrary cuts and corrections, in fact, you do not need to compare the position with different start or end points.

But, if you are talking only about a small number of cuts, performance should not be a problem.

For example, even with ten segments you have only nine comparisons, and not a huge amount of calculations.

Of course, you can always turn the situation into a formula formula (for example, ax^4 + bx^3 +cx^2 + dx + e ) generated using simultaneous equations, which will give you a segment, but the highest power tends to grow considering number of segments, so this is not necessarily as effective as simple checks.

Answer 3

You will not do better than lg n using the comparison algorithm. Re-interpreting the 31 non-sign bits of the IEEE positive float as a 31-bit integer is an order-preserving transformation, so Van Emde Boas attempts and trees are options. I would direct you first to a three-level trie.

Answer 4

You can assign an integer to each position, and then use it as an index in the search table, which will give you a constant search. This is pretty easy if your stick is short and you don't cut it into pieces up to a millimeter long. If you can walk with such an approximation, this will be my way.

There is one advanced method that extends it even further. In each element of the search table, you save the middle position and segment identifier on the left and right. This does one search (O (1)) plus one comparison (O (1)). The disadvantage is that the lookup table should be so large that you never have more than two different segments in the same range of table elements. Again, it depends on your requirements and input, whether it works or not.