MathGroup Archive 2004

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

Search the Archive

Re: Need code to calculate the Lower Envelope for a set of (non collinear) points.

  • To: mathgroup at smc.vnet.net
  • Subject: [mg51445] Re: [mg51409] Need code to calculate the Lower Envelope for a set of (non collinear) points.
  • From: DrBob <drbob at bigfoot.com>
  • Date: Sun, 17 Oct 2004 03:06:28 -0400 (EDT)
  • References: <200410160820.EAA23705@smc.vnet.net>
  • Reply-to: drbob at bigfoot.com
  • Sender: owner-wri-mathgroup at wolfram.com

I think this does it if the data is already sorted:

LowerEnvelope[a_]:=Module[{hull=ConvexHull@a},
     a[[hull/.{x___,1,y___}:>{1,y,x}
         /.{x__,Length@a,y___}:>{x,Length@a}]]
     ]
LowerEnvelope@a
MultipleListPlot[{%,a},PlotJoined\[Rule]True,PlotStyle\[Rule]{Hue[.6]}]

{{4,2},{8,3},{16,5},{44,13},{92,31},{688,269},{992,421},{1000,491}}

If the data might NOT be pre-sorted, the function would be:

LowerEnvelope[a_] := Module[{data = Sort@a, hull},
     hull = ConvexHull@data;
     data[[hull /. {x___, 1, y___} :> {1, y, x}
          /. {x__, Length@a, y___} :> {x, Length@a}]]
     ]

Testing with a random reordering of a still gives the same answer:

LowerEnvelope[Sort[a, Random[] < 0.5 &]]
MultipleListPlot[{%, a}, PlotJoined -> True, PlotStyle -> {Hue[.6]}]

{{4, 2}, {8, 3}, {16, 5}, {44, 13}, {92, 31}, {688, 269}, {992, 421}, {1000, 491}}

Bobby

On Sat, 16 Oct 2004 04:20:45 -0400 (EDT), Gilmar Rodr?guez Pierluissi <gilmar.rodriguez at nwfwmd.state.fl.us> wrote:

> Dear Mathematica Solver Group:
>
> I'm looking for a program to calculate the Lower Envelope
> ("LE" for short)for a set of (non-collinear) points on the
> plane. Please download the following file containing an
> arbitrary set of such points(which I'm calling "A") by
> double-clicking the following shortcut:
>
> http://gilmarlily.netfirms.com/download/A.txt
>
> You can also down load:
>
> http://gilmarlily.netfirms.com/download/Lower Envelope.nb
>
> to evaluate the following steps using Mathematica (version 5):
>
> If your define your working directory as C:\Temporary, then kindly
> evaluate the following Mathematica commands:
>
> In[1]: A = ReadList["C:\\Temporary\\A.txt", {Number, Number}];
>
> Next, plot the set A:
>
> In[2]: plt1 = ListPlot[A, PlotJoined -> True, PlotStyle -> {Hue[.7]}]
>
> I can manipulate the program ConvexHull to find the Lower Envelope
> for the set A as follows:
>
> In[3]: << DiscreteMath`ComputationalGeometry`
>
> In[4]: convexhull = ConvexHull[A]
>
> The following input gives a picture of the Convex Hull:
>
> In[5]: plt2 = ListPlot[Table[A[[convexhull[[i]]]], {i,
>         1, Length[convexhull]}], PlotJoined -> True, PlotStyle -> {Hue[.6]}]
>
> Modifying the starting value of index i in In[5] above
> (starting at i=96 instead of i=1) gives a picture of the
> Lower Envelope of A:
>
> In[6]:plt3 = ListPlot[Table[A[[convexhull[[i]]]], {i,
>         96, Length[convexhull]}], PlotJoined -> True, PlotStyle -> {Hue[.6]}]
>
> In[7]: Show[plt1, plt3]
>
> The Lower Envelope of A ("LEA" for short) is given by:
>
> In[8]: LEA = Table[A[[convexhull[[i]]]], {i, 96, Length[convexhull]}]
>
> So my question is: How can the code of the ConvexHull program be modified,
> to get a program that calculates the LE of a set?
>
> The following (clumsy)alternative attempt:
>
> In[9]: LE[B_] := Module[{M}, {L = Length[B]; M = {};
>     AppendTo[M, B[[L]]]; {Xg, Yg} = B[[L]]; Do[If[B[[
>       L - i + 1]][[2]] < Yg, {{Xg, Yg} = B[[L -
>       i + 1]], AppendTo[M, B[[L - i + 1]]]}], {i, 1, L - 1}]}; Sort[M]]
>
> In[10]: LE[A]
>
> In[11]: plt4 = ListPlot[LE[A], PlotJoined -> True, PlotStyle -> {Hue[.1]}]
>
> In[12]: Show[plt1, plt4]
>
> gives me something that is "not even close, and no cigar".
>
> What I need is an algorithm that gives me the Lower Envelope E of A
> as shown in In[8] above.  Thank you for your help!
>
>
>
>



-- 
DrBob at bigfoot.com
www.eclecticdreams.net


  • Prev by Date: Re: Re: Re: Re: Calculus : limits
  • Next by Date: Re: Re: Sorting a list of pairs on the second elements
  • Previous by thread: Need code to calculate the Lower Envelope for a set of (non collinear) points.
  • Next by thread: Re: Need code to calculate the Lower Envelope for a set of (non collinear) points.