RE: Interval arithmetic, of a sort

• To: mathgroup at smc.vnet.net
• Subject: [mg33776] RE: [mg33721] Interval arithmetic, of a sort
• From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
• Date: Tue, 16 Apr 2002 03:50:24 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```> -----Original Message-----
> From: DIAMOND Mark R. [mailto:dot at dot.dot]
To: mathgroup at smc.vnet.net
> Sent: Wednesday, April 10, 2002 6:49 AM
> To: mathgroup at smc.vnet.net
> Subject: [mg33776] [mg33721] Interval arithmetic, of a sort
>
>
> I cannot find any solution to this problem without using very
> time consuming
> procedural programming, and yet it seems that it ought to
> have a reasonably
> simple functional solution. BTW: Even though I don't use it in the
> following, I am familiar with the Interval notation and functions.
>
> The origin of the programming problem is most easily pictured
> as one of
> laying down numbered strips of cardboard on top of one
> another within an
> interval. For simplicity, assume that the total interval is
> Interval[{0,100}], which I will just write as {0,100}, and it
> has the value
> 1, with the notation now being {1,{0,100}}
>
> Uniquely numbered strips of card are put on top of this one;
> they may or may
> not overlap; I want to be able to obtain a description of the
> visible bits
> of card at the end. So for example, if "+" indicates laying down a new
> {{1,{0,100}}}, then {{{1,{0,100}}} + {2,{2,3}} =
> {{1,{0,2}},{2,{2,3}},{1,{3,100}},
>  indicating that the original strip is visible from 0-2,
> strip 2 is visible
> from 2-3, and the original is again visible from 3-100.
> Continuing, complete
> occlusion would happen with
> {{1,{0,2}},{2,{2,3}},{1,{3,100}}, + {3,{1,20}} =
> {{1,{0,1}},{3,{1,20}},{1,{20,100}}}; again continuing,
> overlap would happen
> with
> {{1,{0,1}},{3,{1,20}},{1,{20,100}}}  + {4,{15,30}} =
> {{1,{0,1}},{3,{1,15}},{4,{15,30}},{1,{30,100}}}
>
> Mark R. Diamond
> No spam email ROT13: znexq at cfl.hjn.rqh.nh
> No crawler web page ROT13 uggc://jjj.cfl.hjn.rqh.nh/hfre/znexq
>
>
>
>

Mark,

here another solution. If you stack up high your intervals, it might be of
advantage to locate the new overlayed Interval by binary search. To do that
I'd propose a simplified data structure for your problem, which only marks
the beginning of an interval; the end ist the just the beginning of the the
next one.

<< DiscreteMath`Combinatorica`

?BinarySearch

The overlaying function is:

Attributes[overlay] = {HoldFirst}

overlay[l_, {layer_, {start_, stop_}}] /; start <= stop :=
Module[{firstx = Floor[BinarySearch[l, start, Last]],
lastx = Floor[BinarySearch[l, stop, Last]]},
l = Join[Take[l, firstx],
{{layer, start}, {l[[lastx, 1]], stop}},
Drop[l, lastx]]
]

l = {{0, -Infinity}}
{{0, -\[Infinity]}}

"blank table", so to speak

overlay[l, {1, {0, 100}}]
{{0, -\[Infinity]}, {1, 0}, {0, 100}}

overlay[l, {2, {2, 3}}]
{{0, -\[Infinity]}, {1, 0}, {2, 2}, {1, 3}, {0, 100}}

overlay[l, {3, {1, 20}}]
{{0, -\[Infinity]}, {1, 0}, {3, 1}, {1, 20}, {0, 100}}

overlay[l, {4, {15, 30}}]
{{0, -\[Infinity]}, {1, 0}, {3, 1}, {4, 15}, {1, 30}, {0, 100}}

Now you can revert to your notation with:

(Transpose[{#1, Partition[#2, 2, 1, {1, 1}, Unevaluated[Infinity]]}] &) @@
Transpose[l]
{{0, {-\[Infinity], 0}},
{1, {0, 1}}, {3, {1, 15}}, {4, {15, 30}}, {1, {30, 100}},
{0, {100, \[Infinity]}}}

I you like, cut off the rests of the table-linen hanging down on both sides.

FromCharacterCode[(If[97 <= # <= 122, Mod[# + 13, 26, 97], #] &) /@
ToCharacterCode["tbbq yhpx\n\n--\nHnegzhg"]]

```

• Prev by Date: Re: Optional
• Next by Date: ReadList under Mac OS X and Mac OS 9
• Previous by thread: Re: Interval arithmetic, of a sort
• Next by thread: Seminar on Computational VaR using Mathematica