Алгоритм вычислительной геометрии множества точек

Question

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

Учитывая набор P из n точек, определите значение A> 0 так, чтобы преобразование сдвига (x, y) -> (x + Ay, y) не меняло порядок (в направлении x) точек с неравным х-координаты.

У меня много трудностей, даже я не могу понять, с чего начать.

Любая помощь с этим будет принята с благодарностью!

Спасибо!

Answer 1

Предположим, что все координаты x, y являются положительными числами.(Без ограничения общности можно добавить смещения.) За время O (n log n) отсортируйте список L точек, в основном в порядке возрастания по координатам x и во вторую очередь в порядке возрастания по координатам y.За время O (n) обработайте пары точек (в порядке L) следующим образом.Пусть p, q будут любыми двумя последовательными точками в L, и пусть px, qx, py, qy обозначают их значения координат x и y.Оттуда вам просто нужно рассмотреть несколько случаев, и должно быть очевидно, что делать: если px = qx, ничего не делать.Иначе, если py <= qy, ничего не делать.В противном случае (px> qx, py> qy) требуется, чтобы px + A * py т.е. (px-qx) / (py-qy)> A.

Итак: Пройдите по порядку L и найдите наибольшее A ', которое удовлетворяется для всех пар точек, где px> qx и py> qy.Затем выберите значение A, немного меньшее, чем A ', например, A' / 2.(Или, если целью проблемы является найти наибольшее такое A, просто сообщите значение A '.)

Answer 2

Хорошо, вот грубый удар по методу.

Сортировка списка точек по x порядку.(Это дает O (nlogn) - все следующие шаги - O (n).)

Создайте новый список dx_i = x_ (i + 1) - x_i, различий между координатами x.Поскольку x_i упорядочены, все эти dx_i> = 0.

Теперь для некоторого A преобразованный dx_i (A) будет x_ (i + 1) -x_i + A * (y_ (i + 1)) - y_i).Будет изменение порядка, если оно будет отрицательным или нулевым (x_ (i + 1) (A)

). Поэтому для каждого dx_i найдите значение A, которое составит dx_i (A) ноль, а именно: A_i = - (x_ (i + 1) - x_i) / (y_ (i + 1) - y_i). Теперь у вас есть список коэффициентов, который «вызовет» порядок обмена между последовательными (в x-порядок) пара точек. Следите за делением на ноль, но это тот случай, когда две точки имеют одинаковый у, эти точки не будут менять порядок. Некоторые из A_i будут отрицательными, откажитесь от них, как вы хотите A> 0. (Отрицательный A_i также вызовет обмен ордерами, поэтому требование A> 0 немного произвольно.)

Найдите наименьшее A_i> 0 в списке. Поэтому любой A с 0

Answer 3

Я думаю, у = 0.

When x = 0, A > 0
(x,y) -> (x+Ay,y)
      -> (0+(A*0),0) = (0,0)
When x = 1, A > 0
(x,y) -> (x+Ay,y)
      -> (1+(A*0),0) = (1,0)

с неравными x-координатами, (2,0), (3,0), (4,0) ... Итак, я думаю, что начальная точка может быть (0,0), х = 0.