Разделение плоскости точек на две равные половины

Ответ 1

Я предположил, что точки различны, иначе даже такая строка не может быть.

Если точки различны, то такая строка всегда существует и ее можно найти с использованием детерминированного алгоритма времени O (nlogn).

Скажем, что точки P1, P2,..., P2n. Предположим, что они не все на одной линии. Если бы они были, то мы могли бы легко сформировать линию расщепления.

Сначала переведите точки так, чтобы все координаты (x и y) были положительными.

Теперь предположим, что у нас магически была точка Q на оси y такая, что ни одна линия, образованная этими точками (т.е. любая бесконечная прямая Pi-Pj) не проходит через Q.

Теперь, поскольку Q не лежит в выпуклой оболочке точек, нетрудно видеть, что мы можем упорядочить точки вращающейся линией, проходящей через Q. Для некоторого угла поворота половина точек будет лежать с одной стороны и другая половина будет лежать на другом из этой вращающейся линии или, другими словами, если мы рассмотрим точки, отсортированные по наклону линии Pi-Q, мы могли бы выбрать наклон между (медианным) th и (медианным +1) -й точки. Этот выбор может быть выполнен в O (n) времени с помощью любого алгоритма выбора времени без необходимости фактической сортировки точек.

Теперь, чтобы выбрать точку Q.

Скажем, что Q было (0, b).

Предположим, что Q коллинеарен P1 (x1, y1) и P2 (x2, y2).

Тогда имеем, что

(y1-b)/x1 = (y2-b)/x2 (заметим, что мы перевели точки так, чтобы xi > 0).

Решение для b дает

b = (x1y2 - y1x2)/(x1-x2)

(Обратите внимание, что если x1 = x2, то P1 и P2 не могут быть коллинеарными с точкой на оси Y).

Рассмотрим | b |.

| б | = | x1y2 - y1x2 |/| x1 -x2 |

Теперь пусть xmax будет x-координатой самой правой точки, а ymax - координатой самого верхнего.

Также пусть D - наименьшая ненулевая разность координат x между двумя точками (это существует, поскольку не все xis одинаковы, так как не все точки являются коллинеарными).

Тогда мы имеем, что | b | <= xmax * ymax/D.

Таким образом, выберите точку Q (0, b) так, чтобы | b | > b_0 = xmax * ymax/D

D можно найти в O (nlogn) времени.

Величина b_0 может стать довольно большой, и нам, возможно, придется решать проблемы точности.

Конечно, лучшим вариантом является выбор Q случайным образом! С вероятностью 1 вы найдете нужную вам точку, что обеспечит ожидаемое время работы O (n).

Если бы мы могли найти способ выбрать Q в O (n) времени (найдя какой-то другой критерий), то мы можем сделать этот алгоритм за время O (n).

Ответ 2

• Создайте произвольную строку на этой плоскости. Проецируйте каждую точку на эту строку a.k.a для каждой точки, получите ближайшую точку на этой линии к этой точке.

• Закажите эти точки вдоль линии в любом направлении и выберите точку на этой линии так, чтобы на одной линии в любом направлении было одинаковое количество точек.

• Получить линию, перпендикулярную первой строке, проходящей через эту точку. Эта линия будет иметь половину исходных точек с каждой стороны.

При этом можно избежать некоторых случаев. Самое главное, если все точки находятся на одной линии, не выбирайте перпендикулярную линию, которая проходит через нее. Фактически, выберите эту линию, поэтому вам не нужно беспокоиться о проецировании очков. Что касается фактической математики, то векторные прогнозы будут очень полезны.

Ответ 3

Это модификация Разделение плоскости точек на две равные половины, которая допускает случай с перекрывающимися точками (в этом случае он скажет, будет или нет ответ существует).

If number of points is odd, return "impossible".

Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
    (i.e. we pretend this line is our new X'-axis, and write down the
     X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
    (`O(N)` or faster-if-desired operation)
    (returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians

In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).

Это O(N) в отличие от других предлагаемых решений.

Предполагая, что решение существует, вышеупомянутый метод, вероятно, завершится, хотя у меня нет доказательств.

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

For every "critical slope range", perform the above algorithm 
  by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.

Критический угол определяется как угол, который может изменить результат (представьте решение предыдущего ответа, поверните весь набор точек до тех пор, пока одна или несколько точек не поменяют местами с одной или несколькими другими точками, пересекая разделительную линию Есть только конечное число из них, и я думаю, что они ограничены количеством очков, поэтому вы, вероятно, смотрите на что-то в диапазоне O(N^2)-O(N^2 log(N)), если у вас есть перекрывающиеся точки, для подхода с грубой силой.

Ответ 4

Я бы предположил, что хороший способ - сортировать/упорядочивать/упорядочивать точки (например, слева направо), а затем выбирать линию, которая проходит через (или между) среднюю точку [с] в последовательности.

Ответ 5

Есть очевидные случаи, когда решение невозможно. Например. когда у вас есть три кучи очков. Одна точка в точке A, две точки в местоположении B и пять точек в точке C.

Если вы ожидаете некоторого приличного распределения, вы, вероятно, получите хороший результат с помощью алгоритма tlayton. Чтобы выбрать начальный уклон линии, вы можете определить степень всего набора точек и выбрать угол наибольшей диагонали.

Ответ 6

median равномерно делит набор чисел так же, как то, что вы пытаетесь выполнить, и это может быть вычисляется в O (n) времени с использованием алгоритма (запись в Cormen et al лучше, поэтому вы можете посмотреть там вместо этого), Итак, найдите медиану ваших значений x M _x (или ваши значения y M _y, если вы предпочитаете) и установите x = M _x ( или y = M _y), и эта линия будет выровнена по оси и распределит ваши точки одинаково.

Если характер вашей проблемы требует, чтобы на линии находилось не более одной точки (если у вас есть нечетное количество очков в вашем наборе, по крайней мере один из них будет на линии), и вы обнаружите, что произошло (или вы просто хотите защититься от возможности), поверните все свои точки на какой-то случайный угол & theta;, и вычислите медианную из повернутых точек. Затем вы поворачиваете срединную линию, которую вы вычисляете - & theta; и он равномерно разделит точки.

Вероятность случайного выбора & theta; такой, что проблема проявляется снова, очень мала с конечным числом точек, но если это так, попробуйте еще раз с другой тетой.

Ответ 7

Я не знаю, насколько это полезно, я видел подобную проблему...

Если у вас уже есть вектор направленности (иначе говоря, коэффициенты размеров вашей плоскости).

Затем вы можете найти две точки внутри этой плоскости и просто используя формулу midpoint, вы можете найти среднюю точку этой плоскости.

Затем, используя коэффициенты этой плоскости и середины, вы можете найти плоскость, которая находится на равном расстоянии от обеих точек, используя общее уравнение плоскости.

Линия тогда составляла бы выражение одной переменной в терминах другой поэтому вы найдете линию с равным расстоянием между обеими плоскостями.

Существуют разные способы сделать это, например проекцию, используя уравнение расстояния от плоскости, но я считаю, что это усложнит вашу математику.

Ответ 8

Я поднял идею от Морона и продолжал формировать детерминированный O (n) алгоритм.

Я также предполагал, что точки различны и n четно (считается, что алгоритм может быть изменено так, что неравномерное n с одной точкой на разделительной линии также поддерживаются).

Алгоритм пытается разделить точки с вертикальной линией между ними. Это только терпит неудачу, если точки в середине имеют одинаковое значение x. В этом случае алгоритм определяет, сколько точек с одним и тем же значением x должно быть на левом и нижнем сайтах и, соответственно, вращает линию.

Я попытаюсь объяснить на примере. Пусть мы имеем 16 точек на плоскости. Сначала нам нужно получить точку с восьмым наибольшим значением x и точка с 9-м наибольшим значением x. С алгоритмом выбора это возможно в O (n), как указано в другом ответе. Если x-значение этих точек отличается, мы делаем. Мы создаем вертикальную линию между этими двумя точками и который разбивает точки равными.

Проблематично теперь, если значения х равны. Итак, у нас есть 3 набора точек. Это в левой части (x < x _a), посередине (x = x _a) и на правой стороне (x > x _a). Теперь идея состоит в том, чтобы подсчитать точки на левой стороне и подсчитайте, сколько точек из середины нужно туда добраться, так что половина точек находится на той стороне. Мы можем игнорировать правую сторону здесь потому что, если у нас есть половина точек на левой стороне, более половины должно быть с правой стороны.

Итак, пусть у нас есть 3 точки (с = 3) с левой стороны, 6 в середине и 7 с правой стороны (алгоритм не знает счет со средней или правой стороны, потому что это ему не нужно, но мы могли бы также определить его в O (n)). Нам нужно 8-3 = 5 точек от середины, чтобы идти с левой стороны. Точки, которые мы уже получили на первом этапе, теперь бесполезны, потому что они определяются только значением x и может быть любой из точек в середине.

Мы хотим, чтобы 5 точек из середины с самым низким значением y с левой стороны и точка с наивысшим значением y с правой стороны. Снова используя алгоритм выбора, мы получаем точку с 5-м наибольшим значением y и точка с 6-м наибольшим значением y. Обе точки будут иметь значение x, равное x _a, иначе мы бы не дошли до этого шага, потому что будет вертикальная линия.

Теперь мы можем создать точку Q в середине этих двух точек. Это одна точка из результирующей линии. Нужен еще один момент, так что никакие точки с левой или правой стороны не делятся. Чтобы получить эту точку, нам нужна точка с левой стороны, который имеет самый низкий угол (b _h) между вертикальной линией при x _a и линия, определяемая этой точкой и Q. Нам также нужна эта точка с правой стороны (с углом a _g). Новая точка R находится между точкой с нижним углом и точка на вертикальной линии (если нижний угол находится на левой стороне, точка выше Q и если нижний угол находится справа, то точка ниже Q).

Линия, определяемая Q и R, делит точки в середине так что есть четное количество точек с обеих сторон. Он не делит точки слева или справа, потому что если бы эта точка имела бы меньший угол и было бы выбрано для вычисления R.

С точки зрения математика, который должен хорошо работать в O (n). Для компьютерных программ довольно легко найти случай где точность становится проблемой. Пример с 4 пунктами был бы A (0, 100000000), B (0, 100000001), C (0, 0), D (0,0000001, 0). В этом примере Q будет (0, 100000000,5) и R (0,00000005, 0). Который дает B и C с левой стороны, а A и D - с правой стороны. Но возможно, что A и B находятся на разделительной линии, из-за ошибок округления. Или, может быть, только один из них. Поэтому он относится к входным значениям, если этот алгоритм соответствует требованиям.

• получаем две точки P _a (x _a, y _a) и P _b (x _b, y _b)
  которые являются медианами на основе значений x > O(n)
• Если x _a!= x _b, вы можете остановиться здесь
  потому что параллельная линия оси y между этими двумя точками является результатом > O(1)
• получить все точки, где значение x равно x _a> O(n)
• счетные точки со значением x меньше x _a как c > O(n)
• получить нижнюю точку P _c на основе значений y из точек из 3. > O(n)
• получить наибольшую точку P _d на основе значений y из точек из 3. > O(n)
• получить (n/2-c) первую точку P _e на основе значений y из точек из 3. > O(n)
• также получить следующую большую точку P _f на основе значений y из точек из 3. > O(n)
• создайте новую точку Q (x _a, (y _e + y _f)/2) между P _e и P _f> O(1)
• для всех точек P _i вычислить угол a _i между P _c, Q и P _i и
  угол b _i между P _d, Q и P _i> O(n)
• получаем точку P _g с наименьшим углом a _g (с _g > 0 ° и a _g < 180 °) > O(n)
• получить точку P _h с наименьшим углом b _h (с b _h > 0 ° и b _h < 180 °) > O(n)
• если нет P _g или P _h (все точки имеют одинаковое значение x)
  создайте новую точку R (x _a +1, 0) в любом месте, но с другим значением x, чем x _a
  else, если _g меньше, чем b _h
  создайте новую точку R ((x _c + x _g)/2, (y _c + y _g)/2) между P _c и P _g
  остальное
  создайте новую точку R ((x _d + x _h)/2, (y _d + y _h)/2) между P _d и P _h> O(1)
• линия, определяемая Q и R, делит точки > O(1)

Ответ 9

Добавить в M ответ: метод для создания Q (который не так далеко) в O(n log n).

Для начала пусть Q - любая точка на оси y, т.е. Q = (0,b) - некоторые хорошие варианты могут быть (0,0) или (0, (y _max -y _min)/2).

Теперь проверьте, есть ли две точки (x ₁, y ₁), (x ₂, y ₂), коллинеарный с Q. Линия между любой точкой и Q есть y = mx + b; так как b постоянна, это означает, что две точки коллинеарны с Q, если их наклоны m равны. Поэтому определите наклоны m _i для всех точек и проверьте, имеются ли какие-либо дубликаты: (аморитизировано O(n) с использованием хеш-таблицы)

Если все m различны, мы закончили; мы обнаружили, что алгоритм Q и M генерирует строку в шагах O(n).
Если две точки коллинеарны с Q, мы переместим Q только на небольшое количество ε, Q _new= (0, b + ε) и покажем, что Q _new не будет коллинеарным с двумя другими точками.

Критерий для ε, полученный ниже, равен:

ε < mminΔ*xmin

Начнем с того, что наш m выглядит так:

mi = yi/xi - b/xi

Найдем минимальную разницу между любыми двумя различными m _i и назовите ее m _minΔ (O(n log n), например, путем сортировки затем сравнивая различия между m _i и _{я + 1} для всех i)

Если мы перешагиваем b на e, новое уравнение для m становится:

mi,new = yi/xi - b/xi - ε/xi
       = mi,old - ε/xi

Так как ε > 0 и x _i > 0, все m сокращаются, и все они сводятся к максимуму ε/x _min. Таким образом, если

ε/xmin < mminΔ, ie.
ε < mminΔ*xmin

истинно, то два m _i, которые ранее были неравными, будут гарантированно оставаться неравными.

Все, что осталось, это показать, что если m _{1, old}= m _{2, old}, то m _{1, new} =/= м <югу > 2, новыйсуб > . Поскольку оба m _i были уменьшены на величину ε/x _i, это эквивалентно отображению x ₁ =/= x _{2суб > . Если они были равны, то:}

y1 = m1,oldx1 + b = m2,oldx2 + b = y2

Противоречивая наше предположение, что все точки различны. Таким образом, m _{1, new} =/= m _{2, new}, и никакие две точки не являются коллинеарными с Q.

Ответ 10

Вот как я подхожу к этой проблеме (с предположением, что n четно и NO три точки коллинеарны):

1) Поднимите точку с наименьшим значением Y. Пусть назовем точку P.

2) Возьмите эту точку как новую начальную точку, так что все остальные точки будут иметь положительные значения Y после этого преобразования.

3) Для каждой другой точки (осталось n - 1 баллов), подумайте об этом под полярной системой координат. Каждая другая точка может быть представлена ​​радиусом и углом. Вы можете игнорировать радиус и просто сфокусироваться на угле.

4) Как вы можете найти линию, разделяющую точки равномерно? Найдите медиану (n - 1) углов. Линия от точки P до точки с этим средним углом будет равномерно разбивать точки.

Сложность времени для этого алгоритма O (n).