Friday, December 19, 2008

aAlgorithm for finding the bar at large gathering using Newton’s method

Algorithm for finding the bar at a large gathering using Newton’s method

Figure 1 Typical sample of people flaunting delightful beverages, while others remain beveragless.

Last year at the artists against AIDS benefit, I was enjoying the weird art, but was somewhat frustrated that I could not seem to figure out where the bar was, despite my best efforts. About ready to give up I decided to use my 20 years of schooling to come up with a robust method of finding a resource in a large group of people. What follows is the derivation and algorithm.

In order for this to work we must make some assumptions about the group.
Primary to this algorithm is that the group be sufficiently large and uniform to make observations on a sample of the group and apply gradients those samples. Depending on the type of room and the type of resource being sought the minimum total group size could vary from 30 to 70, but typically if it is a group of less that 50 the room size would be small enough that more direct methods could be utilized.

Second, we must assume that the members of the group are moving around the area. If it is obvious that some or all of the members are stationary for an extended period of time then those individuals should be excluded from the calculations. This is often the case where there are tables that people are sitting at.

Finally, the participants have to be, on average, consuming the resource in question at a fairly constant rate. This does not need to be constant over the course of the event, but must be continuous over the time period in question. Thus people will start with a full drink and slowly consume it over 20-40 min. The more variance in the rate of consumption the larger the sample size of the group will need to be. Large deviances from the norm like shots should be identified and discarded.

Figure 2 Vectors measuring the movement of alcoholic beverages in a confined space. The length and direction of the vectors is proportional to the velocity vector multiplied by the percentage of remaining beverage.

Once these criteria have been met the algorithm can be implemented.
First take a survey of all of the individuals in a certain radius from your location. Scale the individual’s movement vectors with the quantity of their drinks and average to obtain a single vector. This vector will show the average movement of the alcohol near you.
Figure 3 Initial sample group and the coresponding vector indicating the negative of the mean alcohol movement in the group.

With this invaluable piece of information we can derive several things. The first and most important is the direction of the bar which is in the opposite of the mean alcohol vector (MAV[1]). One could just start walking tat direction and see where they end, up, but would have substantially more success by moving in the direction opposite the mean alcohol vector, but only 30% of the length of the room, or a suitable distance depending on circumstances.

Figure 4 Second survey at location indicated by MAV[1], including MAV[2]

Once at the new location a new survey can be taken yielding a second mean alcohol vector MAV[2]. Furthermore by comparing the overall glass levels at both locations one may extrapolate the location where the glass levels would be full, and presumably this would also be the location where you would also be able to obtain a full glass.
Figure 5 Second survey point with the inclusion of a vector of the average of MAV[1] and MAV[2] weighted by the mean percentage of remaining beverage at each site.
Figure 6 Predicted location of bar by extrapolating the weighted mean vector for the location where beverage levels will reach 100%. ie. If you find where peoples drinks are full you will fin the bar.

In the extensive testing conducted by the author, this method has typically worked in as little as a single iteration and as many as 4. This is most useful for items with a known maximum and minimum such as beverages, but can also be used to locate cheese trays, chocolate fountains, or any one of a number of other items.
Figure 7 The results of the search method.

Special thanks to Rob Raguet-Schofield for providing the initial figure of randomized vectors, without which none of this would have been possible. Nothe that these figures are meant as a tool for explanation and may not be to scale. Please feel free to point out any questionable methods or overwhelming dorkyness in the comments section.






5 comments:

Cara said...

Sigh. I am going to have to drink all of break to make up for this dorky tirade...now if only I could find a bar...

Teach said...

The next question is, exactly how many bars can one locate in the amount of time it takes John Gutzmer to write a blog? I think the number would definitely be greatly than, but not equal to, 25.

Aimee said...

just making sure Cara has located the bar and is not planning to leave for a LONG time after that post!!

Cole said...

The alternative method of just asking one of those "alcohol vectors" where the bar is is probably too obvious, right? :-P

Melissa said...

yikes.