1
$\begingroup$

Given a set of points $X \subset \mathbb{R}$, one can define the median $m^*$ using optimization.

Namely $m^* = \textbf{argmin}_{m \in \mathbb{R}} \sum_{i \in X} |i - m|$. Here $|.|$ is absolute value. As $m^*$ could not be uniquely define, there could be an interval of $m$ all minimize the function, then apply a $min$ would be my fix to it. The reason behind that is i also care about the minimum value of such objective function, all the $m^*$ would gives the same value.

What if a set of points $Y \subset S^1$ from 1-sphere ?

I can still define the median $n^*$ as $n^* = \textbf{argmin}_{n \in S^1} \sum_{j \in Y} |j - n|$. Here $|.|$ is the shortest distance along the circle between two points. Similarly if there exists an interval of $n$ all minimize the objective, pick the minimum as the desired value. (or any feasible $n$ if that is more efficient)

Is the $n^*$ going to be the conventional median? How can I efficiently find such median?

$\endgroup$
0
$\begingroup$

Your definition of the median isn't actually uniquely defined even in the $X \subset \mathbb{R}$ case if $X$ has a (finite) even number of points. Any number $m$ between the middle two values of $X$ will minimise your optimisation problem. Similarly, the median isn't necessarily uniquely defined in $S^1$ when you define it that way. In particular, if you have an even number of evenly spaced points, then every point in $S^1$ is a median by your definition.

In general, I think you can say that $m\in S^1$ is a local minimum of your objective if and only if there are the same number of points in the clockwise half-circle from $m$ as there are in the anticlockwise half-circle. This will be constant on intervals where there aren't any points in $X$ or any points opposite a point in $X$. So you just need to create a copy $X'$ of $X$ shifted halfway around the circle, then for each interval between points in $X \cup X'$, count the points of $X$ in the half-circles on each side of (any point in) that interval.

$\endgroup$
1
  • $\begingroup$ you are 100% right, thanks for pointing out, i'll probably add a minimum to the range of possible values. and i'm also interested in the minimum value of that function, do you know if there is an efficient way to get on the circle? (i'll update the question) $\endgroup$
    – peng yu
    Sep 15 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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