3
$\begingroup$

Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we would like to find the hyperplane passing through the origin, which contains the maximum number of $x_i$'s on one side. Any pointers to equivalent problems, or (in)exact algorithms?

Improve this question
$\endgroup$
9
  • $\begingroup$ If the points are in general position, there is a simple bruteforce algorithm in $O(n^k)$ time: simply consider all hemispheres that have their boundary aligned with a $(k-1)$-tuple of the points. Are you looking for some faster? $\endgroup$
    – Timothy Budd
    Commented Nov 23, 2022 at 8:07
  • 2
    $\begingroup$ I guess a quick $O(n)$ heuristic would be to pick the hyperplane that is normal to the vector pointing from the origin to the center of mass. I can think of some pathologic configurations where this fails spectacularly, but for more generic configurations, it should yield a good first approximation. $\endgroup$
    – mlk
    Commented Nov 23, 2022 at 10:55
  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/4583251/… $\endgroup$
    – RobPratt
    Commented Nov 24, 2022 at 3:33
  • 1
    $\begingroup$ Another way to phrase your question: Find an optimal $2$-cluster partition via hyperplanes through the origin. This may help in searches. $\endgroup$
    – Joseph O'Rourke
    Commented Nov 28, 2022 at 0:29
  • 1
    $\begingroup$ Someone asked a question about equivalent to this again. mathoverflow.net/questions/444144/… I wonder why this question was upvoted but closed the first time, but it attracted multiple answers, upvotes, and upvoted answers the second time. I think it is an interesting mathematical question even if is best solved using inexact algorithms.. $\endgroup$
    – Joseph Van Name
    Commented Apr 7, 2023 at 17:14

0

Reset to default

You must log in to answer this question.