On Fri, 5 Jun 1998 11:54:30 -0700 (PDT), Andrew Wilson
<Andrew_Wilson@geoworks.com> wrote:
>
>>On a side note, this sounds a lot like the traveling salesman puzzle where one
>>tries to find the quickest route for a salesman that must visit a bunch of
>>cities.
>
> Ooooh. Good insight, Zonn! I didn't see this connection before.
>
> Yah, finding the *optimal* route is NP-complete (meaning no
>polynomial-time algorithm exists), but given an arbitrary unsorted set of
>line segments you generally can order them such that the total time to draw
>them is (possibly significantly) shorter than the time to draw the original
>unsorted set. It's only finding the optimal ordering that is hard.
Very true! (I left out that part for effect. ;^) , but looking through those
sort algorithms, they certainly didn't look like the kinda thing you could do
forty times a second real time!
One did guarantee a path that was shorter than twice optimal though...
From an engineering point of view (what I'm good at, I have to take other
peoples word on the math stuff...), I'd say add the wait state between large
trace swings and leave the order alone! ;^)
-Zonn
<><><><><><><><><><><><><><><><><><><><><><><><><><><><
------ ___ Member of A.A.C.S.:
|---- | ( ) Association for Artistically
/ / ( () ) Challenged Signatures
/ / //\\ // (__)
/ ---/ // \\ //\\ // zonn @ zonn . com
-------| // \\/
Received on Fri Jun 5 12:28:58 1998
This archive was generated by hypermail 2.1.8 : Fri Aug 01 2003 - 00:31:38 EDT