Полушарие, в котором лежит максимальное число точек

[alhimikoff]

По сфере разбросаны точки. Как найти полушарие, в котором лежит максимальное число точек?
За $O(n^3)$ так:
Перебираем пары точек. Рассекаем шар плоскостью через две точки и центр. Смотрим сколько точек в полушариях.
А побыстрее?

[alhimikoff]

Откуда надо посмотреть на Землю, чтобы увидеть больше всего городов?

[INGELRII]

За $O(n)$: перебираем точки. Через центр проводим плоскость перпендикулярно лучу, соединяющему центр и перебираемую точку. Смотрим. Пойдет?

[arseniiv]

Есть способ за $O(n^2\log n)$, но я не сам его придумал, так что не буду пока здесь писать.

INGELRII в сообщении #1259812 писал(а):

Через центр проводим плоскость перпендикулярно лучу, соединяющему центр и перебираемую точку. Смотрим. Пойдет?

Получается в целом квадратично, но проверка только $n$ окружностей указанного вида недостаточна. Представьте череду равноотстоящих точек малого круга, близкого к большому, и больше ничего. Мы можем схватить их все, но не центрированными на них экваторами, а окружностью с центром, почти максимально далёким от них.

[svv]

INGELRII

alhimikoff в сообщении #1259517 писал(а):

Рассекаем шар плоскостью через две точки и центр.

Судя по этой фразе, точки на плоскости трактуются в нашу пользу — мы их можем отнести к любому полушарию. Пусть даны 8 точек — вершин куба, вписанного в сферу. Тогда мы можем заполучить аж шесть точек, если проведём плоскость через две диагонали куба. Но если перпендикулярный плоскости луч всегда проходит через одну из точек, получим лишь четыре.

[arseniiv]

(В каноніческом™ варианте полусфера открытая, и выйдет тоже только четыре.)

[venco]

Да возьмите тетраэдр. Полусфера с центром в точке содержит только её. А противоположная полусфера - целых 3.

[slavav]

Для одной точки рассмотрим множество нормалей полупространств, которые содержат эту точку. Это будет полусфера с центром в этой точке. Чтобы её построить надо провести большой круг. С одной стороны от большого круга напишем единицу, с другой ноль - сколько точек содержит полупространство.
Если точек много, то надо нарисовать много таких кругов. Они разобьют сферу на области - грани. В каждой грани сложим числа от всех больших кругов на сфере. Найдём грань с минимальным числом.
Анализ: если точки в общем положении то $n$ кругов породит граф с $n(n-1)$ вершиной. Степени всех вершин - четыре. Граф планарный. По формуле Эйлера имеем $O(n^2)$ граней. Весь граф можно обойти поиском в ширину (по граням, фактически обходим двойственный граф) за $O(n^2)$. При обходе можно поддерживать число в этой грани - когда вы переступаете через ребро графа число меняется на единицу очевидным образом.
Сколько времени нужно чтобы построить граф? Я тут вижу аналогию с упорядочением прямых на плоскости и зонной теоремой. Там на построение графа тратится $O(n^2\log n)$.