MathGroup Archive 1996

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

Search the Archive

Re: programming competition

In article <52664j$8dh at>, xah at says...
>This is a programming problem I recently encountered. The problem has the 
>attraction of being a programming competition type. I post the problem and 
>solution here and hope someone will enjoy and maybe come out with other 
>Suppose you have a ordered list {p1, p2, ... , pn} where points has the 
>{x,y}. You want to modify the list so any neighboring points will have a 
>less or equal to a given value maxLength. You do this by adding points in 
>points. For example, suppose p3 and p4 has length greater than maxLength. 
Your new 
>list should then be
>{p1, p2, p3, newP1, newP2,..., newPm, p4, p5, ... , pn} where 
>newP1, ...newPm lies on the line p3 p4.
>linearInterpolate::usage = "
>linearInterpolate[{p1,p2,...}, maxLength ] returns
>{P1,P2,...} such that the length between neighboring points
>P[i], P[i+1] is less or equal to maxLength.
>Newly created points lies on a line between old points";
Hi, Xah:

I want to enter two functions to your competition. As pointed out by 
Bob Hall your function gives the points in a different order than what
you specify (I guess this is not important to your applications). However
I do not encounter the divide by zero problem mentioned by Bob Hall.
(can it be machine dependent ??)

My first entry is a straight forward Do loop approach. All the clever stuff 
in it, is stolen from you. Also, thanks a lot to Daniel Lichtblau for his 
resent informative article.

linearInterpolateEH1[ li_List, maxLength_ ]:=
Module[{res={}, p1, p2, n},
      {p1, p2} = li[[{i, i+1}]];
      n = Max[Ceiling[Sqrt[#.#]&[N[p2-p1]]/maxLength],1];
      res = {res,Table[p1+(p2-p1)j,{j,0,1-.5/n,1./n}]},
   {i, 1, Length[li]-1}];
   Partition[Flatten[{res, Last[li]}],2]

My second entry is basically the same thing with the Do loop replaced with
a Table. This makes it slightly more compact and faster, but in my opinion
it is more difficult to read and debug.

linearInterpolateEH2[ li_List, maxLength_ ]:=
Module[{p1, p2, n},
 Append[Join @@ Table[{p1, p2} = li[[{i, i+1}]];
  n = Max[Ceiling[Sqrt[#.#]&[N[p2-p1]]/maxLength],1];
    {i,1,Length[li]-1}], Last[li] ]

Bellow are some timings where I also quote Bob Halls solution,
"insertPoints". I think my functions are of linear order in both 
length (li) and resolution (1/maxLength). I suspect yours
to be of second order in the length. Bobs function interpolates with
not equidistant points so it's result can not be directly compared
with the other results.

li =  Join[ {{0,0},{1,1}},
        Table[{i,1}, {i,1,2,1/5}],
        {{2,1}, {3,3}}
Sort[linearInterpolate[li, 0.2] ]  ==
Sort[linearInterpolateEH1[li, 0.2] ] ==
Sort[linearInterpolateEH2[li, 0.2] ]


li = Table[{i,i},{i,100}];

Map[First, {
Timing[linearInterpolate[li, 0.1] ],
Timing[insertPoints[li, 0.1] ],
Timing[linearInterpolateEH1[li, 0.1] ],
Timing[linearInterpolateEH2[li, 0.1] ]}]

{6.15 Second, 5.16 Second, 4.95 Second, 4.89 Second}

li = Table[{i,i},{i,1000}];

Map[First, {
Timing[linearInterpolate[li, 1] ],
Timing[insertPoints[li, 1] ],
Timing[linearInterpolateEH1[li, 1] ],
Timing[linearInterpolateEH2[li, 1] ]}] 

{39.61 Second, 11.04 Second, 13.07 Second, 12.8 Second}




  • Prev by Date: Re: Mathematica and PPP
  • Next by Date: ArcTan[-Cotan[theta]]
  • Previous by thread: Re: programming competition
  • Next by thread: Re: programming competition