Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $N$ points on a circle, where the distance between any two points is the distance measured along the circle, how do I find the median point? If we let the circle have unit circumference, define the median $m$ as the point such that there are an equal number of points clockwise a distance no greater than $1/2$ versus points counter-clockwise a distance no greater than $1/2$.

EDIT

After joriki and an anon pointed out, this 'median' isn't necessarily a unique point. How then could one find any of these median points? Presumably one could check each point, but I'd be interested in a faster way.

share|improve this question
1  
"distance between any two points is the distance measured along the circle" - small arc or big arc? –  J. M. Aug 4 '11 at 16:12
    
Presumably small arc, as usual. –  anon Aug 4 '11 at 16:16
    
@J.M. I was envisioning the distance as an angular separation between two points. For example, if two points are on the positive x and y axes respectively than the distance would be 1/4. I'm not sure if that's big arc or small arc. –  Hooked Aug 4 '11 at 16:16
    
@Hooked: There's always a long way and a short way around a circle (except when they're equally long). You're talking about the short way. –  anon Aug 4 '11 at 16:18
    
@anon, I thought as much, but I was (obliquely I guess) having Hooked clarify his question. :) –  J. M. Aug 4 '11 at 16:19
show 2 more comments

3 Answers

up vote 1 down vote accepted

I thought this question had an interesting flavor to it despite the non-uniqueness discussed in joriki's post. So I'll not worry about that, and instead I'll just consider the task of finding a 'median'. I think this numerical method-like approach will work well.

I have different methods for odd and even numbers of points on the circle. Odd is easier. I think we can quickly agree that for an odd number of points, a median must either lie on a point or lie diametrically opposed to a point (otherwise, an odd number of points can never be cut into two portions of the same parity). We can also see that these two cases are equivalent, and that what we're really looking for is a median-chord, i.e. a diameter of the circle that puts half of the points on one side and the other on the other. So just test all of the points, and you'll find a median.

Now suppose we have an even number of points on the circle. This is the more entertaining part. To examine this part, I would like to describe a process and rely on a sort of discrete intermediate value property.

Suppose we reformulate the problem as drawing a diameter, as I mentioned above, and counting the number of points on each side. Further, associate one side of the diameter with positive values and the other with negative, and call the Sum the sum of these two (one positive, one negative) numbers. We look for when the Sum is zero. Then the process of rotating the diameter follows a sort of discrete intermediate value property, where the Sum will change in absolute value by 0, 1, or 2 only. 1 can only happen when the diameter lies on a point.

Now, for the process itself. Calculate the Sum from the diameter at each of the even points. If any of these results in a Sum of zero, then we are done (use that diameter). If not, then there exists a positive Sum point adjacent to a negative Sum point. Then such a diameter passes through the space between these two points. Fortunately, only a finite number of spots need to be checked - only where the diameter crosses over a point (in this case, on the opposite side, and you should really just look at their Sums instead, but so be it).

Finally, I want to note that there does always exist a median. And I wanted to note that while writing this up, I didn't end up using the IVP nearly as much as I thought I would.

share|improve this answer
add comment

To "define the median $m$ as the point such that there are an equal number of points clockwise a distance no greater than $1/2$ versus points counter-clockwise a distance no greater than $1/2$", you'd first have to show that there is only one such point. This will generally not be the case. This is not just, as for the "normal" median, because of degenerate situations of which there is only a set of measure zero; there can be several such points even if the points are in general position. To see this, imagine an odd number $n$ of points equally spaced (i.e. they form a regular $n$-gon), and then move each point by some arbitrary small amount less than a quarter of the distance between points. Then it will still be the case that each of the points has as many points clockwise as counter-clockwise at a distance no greater than $1/2$.

[Edit in response to the edit in the question:]

You don't have to check each point individually (which would be a double loop); a single loop suffices. Cyclically sort the points according to their angles (taking $O(N\log N)$ time), start at some point, and move along the circle clockwise with a second point until you reach a point that's counter-clockwise from the first point. Until you find a median point, move the first and second point in lockstep, alternatingly advancing the second point until it's counter-clockwise from the first and advancing the first until the second is clockwise from it again. Since the two halves of the circle switch sides during the process, there must be some point along the way where they contain the same number of points, and that's the "median" you're looking for.

share|improve this answer
1  
You could also look at the vertices of a $2n$-gon, where literally every single point on the cirlce is a "median point." –  anon Aug 4 '11 at 16:42
    
@anon Wouldn't the $2n$-gon be a one of those degenerate situations of which there is only a set of measure zero? –  Hooked Aug 4 '11 at 17:01
    
I'm not sure how @joriki knows that degenerate situations (configurations with no unique median, or continuum many) are a set of measure zero. –  anon Aug 4 '11 at 17:10
    
@anon: Are you referring to the normal median or the cyclical one defined here? For the normal median, for an odd number points, the median is unique except on a finite union of subspaces of the inputs defined by the pairwise equality constraints, which has measure zero. For the cyclical median, there's a similar set of measure zero, the finite union of the subspaces of the inputs defined by the pairs of points being opposite each other; but I was arguing that the non-uniqueness is worse in this case and can occur in general position, i.e. on a set of non-zero measure. –  joriki Aug 4 '11 at 17:36
    
@joriki: I was referring to cyclical, but now I see your argument was that the cyclical median doesn't really have almost everywhere uniqueness in the configuration space, as I suspected. –  anon Aug 4 '11 at 18:23
add comment

This page has a useful algorithm on it to find the mean angle on a circle:

http://en.wikipedia.org/wiki/Mean_of_circular_quantities

Once you find the mean angle, iterate the set of points and calculate the angle to each one relative to the center of the circle. Subtract the mean angle from each one, and keep track of the one with the smallest absolute value - that's your median point.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.