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.
Best Answer
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.