6
$\begingroup$

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.

  • 0
    Unless one distance among two successive points is substantially bigger then the remaining such distances I don't think that from a practical standpoint the idea of a "median point" makes much sense in this framework.2011-08-04

3 Answers 3

1

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.

2

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.

  • 0
    @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.2011-08-04
1

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.