3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Eppstein Aug 2 '13 at 15:38
  • $\begingroup$ @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? $\endgroup$ – Ecir Hana Aug 2 '13 at 16:11
  • $\begingroup$ 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. $\endgroup$ – David Eppstein Aug 2 '13 at 20:06
  • $\begingroup$ 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)$? $\endgroup$ – Yuval Filmus Aug 5 '13 at 2:55
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 5 '13 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.