Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2002
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
> numbered strip, and if we start with
> {{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]]
  ]

We start with
 
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