[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[SigBio] Re: SIGBio-l Digest, Vol 17, Issue 2



I put a discussion/comparison of the two methods we were considering on the wiki here http://www.acm.uiuc.edu/projects/Cells/wiki/CollisionDetection .

Skip lists allow us to keep a sorted list with O(lg n) or O(1) complexity for all the operations we're going to need.  They also take up less space and perform faster updates than the other method.  I may be wrong about some of those things so make sure but I think we should go with this method.

Cyrus


On 2/2/07, sigbio-l-request@xxxxxxxxxxxx < sigbio-l-request@xxxxxxxxxxxx> wrote:
Send SIGBio-l mailing list submissions to
        sigbio-l@xxxxxxxxxxxx

To subscribe or unsubscribe via the World Wide Web, visit
         https://www-s.acm.uiuc.edu/cgi-bin/mailman/listinfo/sigbio-l
or, via email, send a message with subject or body 'help' to
        sigbio-l-request@xxxxxxxxxxxx

You can reach the person managing the list at
        sigbio-l-owner@xxxxxxxxxxxx

When replying, please edit your Subject line so it is more specific
than "Re: Contents of SIGBio-l digest..."


Today's Topics:

   1. Trac is updated (Cyrus Omar)
   2. Safety meetings and link to Trac (Cyrus Omar)
   3. Re: Safety meetings and link to Trac (Kim Vlcek)
   4. Re: Safety meetings and link to Trac (Kim Vlcek)


----------------------------------------------------------------------

Message: 1
Date: Thu, 1 Feb 2007 23:25:07 -0600
From: "Cyrus Omar" < comar2@xxxxxxxx>
Subject: [SigBio] Trac is updated
To: sigbio-l@xxxxxxxxxxxx
Message-ID:
        < abef605f0702012125v26bcc595n15068e9be4c2c6ce@xxxxxxxxxxxxxx>
Content-Type: text/plain; charset="iso-8859-1"

Hey guys, I put some stuff up on the Trac page.  A summary of todays
meeting, a discussion page for what rules we want to implement, and some
instructions on accessing the code files from the svn repository (you can
download them from the Trac now.)

For those who are not assigned a specific coding task yet, lets start
brainstorming some ideas.  If everyone could at least get one idea down on
that page for next week (or make an existing idea on there more specific)
that'd be great.  For those of you without ACM accounts, just send the idea
to this list so someone else can put it on the wiki (or get an ACM
account.)  If you weren't at the meeting and want access to the wiki let me
know and I'll add you.

By next week everyone should try and get their part of the coding done so we
can move ahead and have something cool for EOH.

Cyrus Omar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www-s.acm.uiuc.edu/pipermail/sigbio-l/attachments/20070201/763de8d6/attachment-0001.html

------------------------------

Message: 2
Date: Thu, 1 Feb 2007 23:44:26 -0600
From: "Cyrus Omar" <comar2@xxxxxxxx>
Subject: [SigBio] Safety meetings and link to Trac
To: sigbio-l@xxxxxxxxxxxx
Message-ID:
        <abef605f0702012144r11225d97o47496d0f3a73a480@xxxxxxxxxxxxxx >
Content-Type: text/plain; charset="iso-8859-1"

Hey guys, I also posted when the safety meetings are (only 2 more left)
which everyone probably needs to go to on the wiki as well.

The URL once again is http://www.acm.uiuc.edu/projects/Cells/wiki/WikiStart.

The tasks everyone has been assigned are up there too.  Kim, if you want to
be involved with the collision detection you two can work on it together
since its the most complicated part.  I put him on it because we discussed a
more efficient way to do after you had left -- basically we impose a maximum
width and height to each element and keep a sorted list of the x locations
of each edge and the y locations of each edge, and only go left and right in
that list far enough that the maximum dimensions aren't violated.  That
prevents having to search through all of the cells but is still more
efficient in the average case than having to look up the cells at every
location within the cell, which would be order O(wh) where w = width, h =
height.

If thats a bit too hard to finish in a week we can work on it next week too.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www-s.acm.uiuc.edu/pipermail/sigbio-l/attachments/20070201/9fc8aef0/attachment-0001.htm

------------------------------

Message: 3
Date: Fri, 2 Feb 2007 01:13:58 -0600
From: "Kim Vlcek" <kvlcek2@xxxxxxxx>
Subject: Re: [SigBio] Safety meetings and link to Trac
To: "Cyborg mayhem / SigBio" <sigbio-l@xxxxxxxxxxxx>
Message-ID:
        < 1065225b0702012313p34c05e85tb06b7b90c8f88e99@xxxxxxxxxxxxxx>
Content-Type: text/plain; charset="iso-8859-1"

hey dudes.

http://www.harveycartel.org/metanet/tutorials/tutorialA.html



On 2/1/07, Cyrus Omar <comar2@xxxxxxxx> wrote:
>
> Hey guys, I also posted when the safety meetings are (only 2 more left)
> which everyone probably needs to go to on the wiki as well.
>
> The URL once again is
> http://www.acm.uiuc.edu/projects/Cells/wiki/WikiStart .
>
> The tasks everyone has been assigned are up there too.  Kim, if you want
> to be involved with the collision detection you two can work on it together
> since its the most complicated part.  I put him on it because we discussed a
> more efficient way to do after you had left -- basically we impose a maximum
> width and height to each element and keep a sorted list of the x locations
> of each edge and the y locations of each edge, and only go left and right in
> that list far enough that the maximum dimensions aren't violated.  That
> prevents having to search through all of the cells but is still more
> efficient in the average case than having to look up the cells at every
> location within the cell, which would be order O(wh) where w = width, h =
> height.
>
> If thats a bit too hard to finish in a week we can work on it next week
> too.
>
> _______________________________________________
> SIGBio-l mailing list
> SIGBio-l@xxxxxxxxxxxx
> https://www-s.acm.uiuc.edu/cgi-bin/mailman/listinfo/sigbio-l
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www-s.acm.uiuc.edu/pipermail/sigbio-l/attachments/20070202/47bbe29b/attachment-0001.html

------------------------------

Message: 4
Date: Fri, 2 Feb 2007 01:47:06 -0600
From: "Kim Vlcek" < kvlcek2@xxxxxxxx>
Subject: Re: [SigBio] Safety meetings and link to Trac
To: "Cyborg mayhem / SigBio" <sigbio-l@xxxxxxxxxxxx >
Message-ID:
        <1065225b0702012347i72386691t205bba1cf6301940@xxxxxxxxxxxxxx>
Content-Type: text/plain; charset="iso-8859-1"

oh yea, i think that your bigO times are off. sorted lists are really
expensive to maintain. im seeing that first algorithm at like... not linear,
even.

On 2/2/07, Kim Vlcek < kvlcek2@xxxxxxxx> wrote:
>
> hey dudes.
>
> http://www.harveycartel.org/metanet/tutorials/tutorialA.html
>
>
>
> On 2/1/07, Cyrus Omar <comar2@xxxxxxxx> wrote:
>
> > Hey guys, I also posted when the safety meetings are (only 2 more left)
> > which everyone probably needs to go to on the wiki as well.
> >
> > The URL once again is
> > http://www.acm.uiuc.edu/projects/Cells/wiki/WikiStart.
> >
> > The tasks everyone has been assigned are up there too.  Kim, if you want
> > to be involved with the collision detection you two can work on it together
> > since its the most complicated part.  I put him on it because we discussed a
> > more efficient way to do after you had left -- basically we impose a maximum
> > width and height to each element and keep a sorted list of the x locations
> > of each edge and the y locations of each edge, and only go left and right in
> > that list far enough that the maximum dimensions aren't violated.  That
> > prevents having to search through all of the cells but is still more
> > efficient in the average case than having to look up the cells at every
> > location within the cell, which would be order O(wh) where w = width, h =
> > height.
> >
> > If thats a bit too hard to finish in a week we can work on it next week
> > too.
> >
> > _______________________________________________
> > SIGBio-l mailing list
> > SIGBio-l@xxxxxxxxxxxx
> > https://www-s.acm.uiuc.edu/cgi-bin/mailman/listinfo/sigbio-l
> >
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://www-s.acm.uiuc.edu/pipermail/sigbio-l/attachments/20070202/2774eb02/attachment-0001.htm

------------------------------

_______________________________________________
SIGBio-l mailing list
SIGBio-l@xxxxxxxxxxxx
https://www-s.acm.uiuc.edu/cgi-bin/mailman/listinfo/sigbio-l


End of SIGBio-l Digest, Vol 17, Issue 2
***************************************



--
Best Regards,
Cyrus Omar