Taren Nauxen (![[info]](http://p-stat.livejournal.com/img/userinfo.gif){kind=small} taren_) wrote,@ 2008-07-12 20:49:00 |
|
Centroids
Warning: Math post
Okay, maybe I'm being stupid here, but let me see if this makes sense to anyone. (Bueller...)
I'm thinking about adding a feature to Total Recall that tries to make a "chain" of players based on Autorival data. Basically, each player is a vertex in R2, and there are edges between players that are rivals. (I guess they'd have to be undirected now...)
The goal of the "chain" is to minimize the lengths of all the edges between points, while keeping all edges a certain length (e.g., 1).
This can be iteratively calculated by "relaxing" each point until no further relaxations can be made. If player A is rivals with B, C, and D, then find the point that minimizes the edges between them all. Repeat for all other points.
What I'm having trouble with is coming up with a way of calculating that optimal point. At first I thought it would be the arithmetic mean of all coordinates, but that's not the case. Here's an example: Consider an isosceles triangle that's 2 units wide at the base and 2 units tall. The singular point that is the closest to all three is sqrt(1/3) (0.5773) up from the center of the base. The arithmetic mean puts this point at 2/3 (0.667)
I've found some articles leading me to believe that I'm actually calculating the centroid of the set of points, not the actual arithmetic mean? From what it seems like, centroids only apply to 2D areas and centers of mass, but there was one article suggesting that it may be related to my application.
Does anyone know where I can find more out about this? Wiki has this: Centroid of a non-overlapping closed polygon but that doesn't help as I'm not working with polygons. I could always write a function that brute-force finds an optimal position (I may have to anyway due to the restriction that |e|>=1)
Anyway, back to your regularly scheduled LJ.
Warning: Math post
Okay, maybe I'm being stupid here, but let me see if this makes sense to anyone. (Bueller...)
I'm thinking about adding a feature to Total Recall that tries to make a "chain" of players based on Autorival data. Basically, each player is a vertex in R2, and there are edges between players that are rivals. (I guess they'd have to be undirected now...)
The goal of the "chain" is to minimize the lengths of all the edges between points, while keeping all edges a certain length (e.g., 1).
This can be iteratively calculated by "relaxing" each point until no further relaxations can be made. If player A is rivals with B, C, and D, then find the point that minimizes the edges between them all. Repeat for all other points.
What I'm having trouble with is coming up with a way of calculating that optimal point. At first I thought it would be the arithmetic mean of all coordinates, but that's not the case. Here's an example: Consider an isosceles triangle that's 2 units wide at the base and 2 units tall. The singular point that is the closest to all three is sqrt(1/3) (0.5773) up from the center of the base. The arithmetic mean puts this point at 2/3 (0.667)
I've found some articles leading me to believe that I'm actually calculating the centroid of the set of points, not the actual arithmetic mean? From what it seems like, centroids only apply to 2D areas and centers of mass, but there was one article suggesting that it may be related to my application.
Does anyone know where I can find more out about this? Wiki has this: Centroid of a non-overlapping closed polygon but that doesn't help as I'm not working with polygons. I could always write a function that brute-force finds an optimal position (I may have to anyway due to the restriction that |e|>=1)
Anyway, back to your regularly scheduled LJ.
