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

Question

Дана двумерная плоскость, в которой есть n точек. Мне нужно сгенерировать уравнение прямой, которая делит плоскость так, чтобы на одной стороне было n / 2 точки, а на другой n / 2 точки. (кстати это не домашняя работа, я просто пытаюсь решить проблему)

Answer 1

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

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

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

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

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

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

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

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

Предположим, что 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. </p>

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

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

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

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

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

Answer 2

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

2. Упорядочите эти точки вдоль линии в любом направлении и выберите точку на этой линии таким образом, чтобы на линии было одинаковое количество точек в любом направлении.

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

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

Answer 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)), если у вас есть перекрывающиеся точки, для подхода грубой силы.

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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

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

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

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

Answer 8

Чтобы добавить к ответу М: метод генерации Q (это не так далеко) в O(n log n).

Для начала, пусть Q будет любой точкой на оси Y, т.е. Q = (0,b) - некоторые хорошие варианты могут быть (0,0) или (0, (у _макс -y _мин ) / 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 _новый не будет коллинеарным с двумя другими точками.

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

ε < m<sub>minΔ</sub>*x<sub>min</sub>

---

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

m<sub>i</sub> = y<sub>i</sub>/x<sub>i</sub> - b/x<sub>i</sub>

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

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

m<sub>i,new</sub> = y<sub>i</sub>/x<sub>i</sub> - b/x<sub>i</sub> - ε/x<sub>i</sub>
       = m<sub>i,old</sub> - ε/x<sub>i</sub>

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

ε/x<sub>min</sub> < m<sub>minΔ</sub>, ie.
ε < m<sub>minΔ</sub>*x<sub>min</sub>

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

---

Осталось только показать, что если m _{1, старый} = m _{2, старый} , то m _{1, новый} = / = m _{2, новый} . Поскольку оба m _i были уменьшены на величину ε / x _i , это эквивалентно показу x ₁ = / = x ₂, Если они были равны, то:

y<sub>1</sub> = m<sub>1,old</sub>x<sub>1</sub> + b = m<sub>2,old</sub>x<sub>2</sub> + b = y<sub>2</sub>

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

Answer 9

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

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

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

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

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

Итак, давайте предположим, что у нас есть 3 точки (c = 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 находятся на разделительной линии из-за ошибок округления.Или, может быть, только один из них.Поэтому он относится к входным значениям, если этот алгоритм соответствует требованиям.

1. получить эти две точки P _a (x _a , y _a ) и P _b (x _b , у _б )
   которые являются медианы, основанные на значениях х > O(n)
2. если x _a ! = X _b , вы можете остановиться здесь
   потому что параллельная ось Y между этими двумя точками является результатом > O(1)
3. получить все точки, где значение x равно x _a > O(n)
4. количество точек со значением x меньше x _a как c > O(n)
5. получить самую низкую точку P _c на основе значений y из точек от 3. > O(n)
6. получить наибольшую точку P _d на основе значений y из точек от 3. > O(n)
7. получить (n / 2-c) наибольшую точку P _e на основе значений y из точек от 3. > O(n)
8. также получают следующую наибольшую точку P _f на основе значений y из точек от 3. > O(n)
9. создать новую точку Q (x _a , (y _e + y _f ) / 2) между P _e и P _f > O(1)
10. для всех точек P _i Рассчитать
    угол a _i между P _c , Q и P _i и
    угол b _i между P _d , Q и P _i > O(n)
11. получить точку P _g с наименьшим углом a _g (с _g > 0 ° и a _g <180 °) <code>> O(n)
12. получить точку P _h с наименьшим углом b _h (с b _h > 0 ° и b _h <180 °) <code>> O(n)
13. если P _g или P _h отсутствуют (все точки имеют одинаковое значение x)
    создать новую точку R (x _a + 1, 0) где угодно, но с другим значением x, чем x _a
    иначе, если a _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)
14. линия, определяемая Q и R, делит точки > O(1)

Answer 10

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

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

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

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

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

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