fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Полушарие, в котором лежит максимальное число точек
Сообщение27.10.2017, 09:29 


27/11/15

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

 Профиль  
                  
 
 Re: Полушарие, в котором лежит максимальное число точек
Сообщение27.10.2017, 10:53 


27/11/15

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

 Профиль  
                  
 
 Re: Полушарие, в котором лежит максимальное число точек
Сообщение28.10.2017, 01:58 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Полушарие, в котором лежит максимальное число точек
Сообщение28.10.2017, 02:49 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Полушарие, в котором лежит максимальное число точек
Сообщение28.10.2017, 02:51 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora
INGELRII
alhimikoff в сообщении #1259517 писал(а):
Рассекаем шар плоскостью через две точки и центр.
Судя по этой фразе, точки на плоскости трактуются в нашу пользу — мы их можем отнести к любому полушарию. Пусть даны 8 точек — вершин куба, вписанного в сферу. Тогда мы можем заполучить аж шесть точек, если проведём плоскость через две диагонали куба. Но если перпендикулярный плоскости луч всегда проходит через одну из точек, получим лишь четыре.

 Профиль  
                  
 
 Re: Полушарие, в котором лежит максимальное число точек
Сообщение28.10.2017, 02:58 
Заслуженный участник


27/04/09
28128
каноніческом™ варианте полусфера открытая, и выйдет тоже только четыре.)

 Профиль  
                  
 
 Re: Полушарие, в котором лежит максимальное число точек
Сообщение28.10.2017, 05:41 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Полушарие, в котором лежит максимальное число точек
Сообщение28.10.2017, 10:14 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: B@R5uk


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group