Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a name or algorithm (besides the naive one) for the following problem. I searched with keywords "line segment covering" but I couldn't make any use of the algorithms I found.

By the naive algorithm I mean the algorithm which first sorts $S$ in ascending order by $x_i$ and then sums up the distances between segments $[x_i,y_i]$.

Inputs:

  • interval $I :=$ [$a$,$b$], $a,b \in \mathbb{Q}$
  • set of intervals $S := \{[x_i,y_i] | i=1,...n, x_i,y_i \in \mathbb{Q} \}$

One can assume that $I \cap [x_i,y_i] \neq \emptyset$.

Output: Overall length of the sub intervals of $I$ which are not covered by $S$.

For example, if $I=[0,5]$ and $S=\{[1,2], [4,20]\}$ the algorithm outputs $3$ ($=|[0,1[|$ + $|]2,4[|$)

share|improve this question
    
This SO question about nearly the same problem did not turn up anything smarter, nor any fancy name for the naive algorithm you describe. –  Henning Makholm Jan 19 '12 at 21:26
    
Thanks for the reference. I need to implement this in a database query. Now that I know there probably isn't better algorithm I can concentrate on optimizing the implementation. –  anonymous Jan 20 '12 at 6:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.