       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>
• 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
> arbitrary set of such points(which I'm calling "A") by
> double-clicking the following shortcut:
>
>
> You can also down load:
>
>
> to evaluate the following steps using Mathematica (version 5):
>
> evaluate the following Mathematica commands:
>
> In: A = ReadList["C:\\Temporary\\A.txt", {Number, Number}];
>
> Next, plot the set A:
>
> In: 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: << DiscreteMath`ComputationalGeometry`
>
> In: convexhull = ConvexHull[A]
>
> The following input gives a picture of the Convex Hull:
>
> In: plt2 = ListPlot[Table[A[[convexhull[[i]]]], {i,
>         1, Length[convexhull]}], PlotJoined -> True, PlotStyle -> {Hue[.6]}]
>
> Modifying the starting value of index i in In above
> (starting at i=96 instead of i=1) gives a picture of the
> Lower Envelope of A:
>
> In:plt3 = ListPlot[Table[A[[convexhull[[i]]]], {i,
>         96, Length[convexhull]}], PlotJoined -> True, PlotStyle -> {Hue[.6]}]
>
> In: Show[plt1, plt3]
>
> The Lower Envelope of A ("LEA" for short) is given by:
>
> In: 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: LE[B_] := Module[{M}, {L = Length[B]; M = {};
>     AppendTo[M, B[[L]]]; {Xg, Yg} = B[[L]]; Do[If[B[[
>       L - i + 1]][] < Yg, {{Xg, Yg} = B[[L -
>       i + 1]], AppendTo[M, B[[L - i + 1]]]}], {i, 1, L - 1}]}; Sort[M]]
>
> In: LE[A]
>
> In: plt4 = ListPlot[LE[A], PlotJoined -> True, PlotStyle -> {Hue[.1]}]
>
> In: 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 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.