<p>(I tried to ask at <a href="https://stackoverflow.com/questions/18014624/constant-time-search">SO</a> but maybe this has more to do with the CS theory.)</p>

<p>Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it belongs to, in constant time?</p>

<p>For example:</p>

<pre><code>  |------------------|---------|---------------|
  0.0                4.5       7.853293843     9.123
</code></pre>

<p>Given a position:</p>

<pre><code>                                   ^
                                   |
                                   8.005
</code></pre>

<p>I would like to get <code>3rd piece</code>.</p>

<p>It is possible to easily get such answer in O(log n) time with binary search but is it possible to do it in O(1)? If I pre-process the "cut" positions somehow? Perhaps there is a data structure which could help to speed the search up?</p>

<p>PS: Is there a name for such problem? I know "rod cutting" refers to a slightly different problem...</p>

CC BY-SA 3.0
2013-08-02T15:38:35.700Z
I don't know of a method for this exact problem, but the alias method (a way of generating elements randomly with given probabilities) does give a length-preserving constant-time map from positions to pieces, but possibly with a scrambled order of the pieces.
David Eppstein
CC BY-SA 3.0
2013-08-02T16:11:23.810Z
@DavidEppstein Thanks for the reply! I'm not familiar with "alias method" but from what I just read, doesn't it work in opposite direction? That is, if I have a segment it can generate some position?
Ecir Hana
CC BY-SA 3.0
2013-08-02T20:06:56.027Z
One interpretation of the alias method is that it scales and reorders the segments so that the segment containing a particular value $x$ can be determined in two steps: rounding $x$ to an integer, and then comparing the fractional part of $x$ against at most one segment boundary that lies between that integer and the next. So then you can generate a random segment by generating a random $x$ and applying this test.
David Eppstein
CC BY-SA 3.0
2013-08-05T02:55:44.383Z
It depends on your computational model. Suppose for example that the pieces have sizes $1/2,1/4,1/8,\ldots,1/2^n,1/2^n$ ($n$ pieces in total). Can you solve your problem in your case in $O(1)$?
Yuval Filmus
CC BY-SA 3.0
2013-08-05T02:57:45.047Z
The alias method can generate a random segment from the rod in proportion to its length. As David mentions, to that end it cuts the large segments (those larger than $1/n$) into pieces and reorders them; the pieces are not contiguous. In the end, each part of length $1/n$ will consist of a piece of a large segment, and possibly a small segment.
Yuval Filmus
CC BY-SA 3.0
2013-08-11T08:02:14.777Z
How do you find this approach:
David G
CC BY-SA 3.0
2013-08-11T08:11:09.770Z
What if you first pre-process the cut positions in such a way, that you can get the desired answer by reading the input bit-by-bit? In your example, you read 8 and this gives 3rd piece. If the input would be 7.852, the algorithm would in first three steps return the position 2-3 and in the next step (after reading digit 2) the answer would be 2.
David G
<ds.algorithms><time-complexity><search-problem>
Constant time search for rod segment
Ecir Hana
# Constant time search for rod segment

(Asked by: username_0 on 2013-08-02)

(I tried to ask at SO but maybe this has more to do with the CS theory.)
Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it belongs to, in constant time?
For example:
  |------------------|---------|---------------|
  0.0                4.5       7.853293843     9.123

Given a position:
                                   ^
                                   |
                                   8.005

I would like to get 3rd piece.
It is possible to easily get such answer in O(log n) time with binary search but is it possible to do it in O(1)? If I pre-process the "cut" positions somehow? Perhaps there is a data structure which could help to speed the search up?
PS: Is there a name for such problem? I know "rod cutting" refers to a slightly different problem...

**Tags:** ds.algorithms, time-complexity, search-problem
> **Comments:**
> **username_1**: I don't know of a method for this exact problem, but the alias method (a way of generating elements randomly with given probabilities) does give a length-preserving constant-time map from positions to pieces, but possibly with a scrambled order of the pieces.  
> **username_0**: @DavidEppstein Thanks for the reply! I'm not familiar with "alias method" but from what I just read, doesn't it work in opposite direction? That is, if I have a segment it can generate some position?  
> **username_1**: One interpretation of the alias method is that it scales and reorders the segments so that the segment containing a particular value $x$ can be determined in two steps: rounding $x$ to an integer, and then comparing the fractional part of $x$ against at most one segment boundary that lies between that integer and the next. So then you can generate a random segment by generating a random $x$ and applying this test.  
> **username_2**: It depends on your computational model. Suppose for example that the pieces have sizes $1/2,1/4,1/8,\ldots,1/2^n,1/2^n$ ($n$ pieces in total). Can you solve your problem in your case in $O(1)$?  
> **username_2**: The alias method can generate a random segment from the rod in proportion to its length. As David mentions, to that end it cuts the large segments (those larger than $1/n$) into pieces and reorders them; the pieces are not contiguous. In the end, each part of length $1/n$ will consist of a piece of a large segment, and possibly a small segment.  
> **username_3**: How do you find this approach:  
> **username_3**: What if you first pre-process the cut positions in such a way, that you can get the desired answer by reading the input bit-by-bit? In your example, you read 8 and this gives 3rd piece. If the input would be 7.852, the algorithm would in first three steps return the position 2-3 and in the next step (after reading digit 2) the answer would be 2.  

---

## 0 answers

