Я исследовал несколько алгоритмов для определения того, лежит ли точка в выпуклой оболочке, но я не могу найти ни одного алгоритма, который мог бы выполнить трюк за время O(logn), и я не могу придумать его сам. Пусть [] быть массивом, содержащим вершины выпуклой оболочки, могу ли я каким-либо образом предварительно обработать этот массив, чтобы можно было проверить, лежит ли новая точка внутри выпуклой оболочки за время O(logn).
Определите, лежит ли точка в выпуклой оболочке за время O (log n)
comment
Вы также можете задать этот вопрос на сайте Mathematics. Похоже, вас больше интересует сам алгоритм, а не реализация.
- person Tim Biegeleisen schedule 02.03.2015
Ответы (1)
Похоже, вы можете.
- Отсортируйте вершины в
a[]по полярному углу относительно одной из вершин (назовем ее A). O(N log N), как вычисление выпуклой оболочки. - Считайте точку, определите ее полярный угол. О(1)
- Найдите две соседние вершины, одна из которых должна иметь полярный угол меньше, чем точка из шага 2, а другая должна иметь угол больше (B и C). O(log N), бинарный поиск
- Затем простая геометрия: нарисуйте треугольник между точками из A, B, C и проверьте, лежит ли внутри точка из шага 2. О(1)
person
Everv0id
schedule
02.03.2015
что такое пт. 1, 2 и 3 в данном случае pt. 1 проверяемая точка и pt. 2 и 3 являются соседними точками, удовлетворяющими условию шага 3?
- person Andrew Brick; 02.03.2015
Также не могли бы вы объяснить, как шаг 3 выполняется за время O (logn), пожалуйста.
- person Andrew Brick; 02.03.2015
нет, извините за мои сокращения :) pt.1 — это пункт 1 (сортировка), pt.2 — это пункт 2 (точка чтения) и т. д.
- person Everv0id; 02.03.2015
о, я понимаю, но точка все еще может не лежать на линии, соединяющей соседние точки, и все еще находиться в выпуклой оболочке
- person Andrew Brick; 02.03.2015
Кажется, я неправильно понял вашу проблему. Вы имеете в виду, что точка может лежать внутри выпуклой оболочки?
- person Everv0id; 02.03.2015
да, я проверяю, лежит ли он внутри выпуклой оболочки, а не только на краю выпуклой оболочки
- person Andrew Brick; 02.03.2015
на шаге 4 вы проверяете, содержится ли треугольник в выпуклом множестве, но я не думаю, что это можно сделать за время O (1), есть ли способ сделать это за время O (logn)
- person Andrew Brick; 02.03.2015
Неа. На четвертом шаге у нас уже есть точки A, B, C. Если проверяемая точка лежит вне треугольника ABC, значит, она лежит вне всей выпуклой оболочки.
- person Everv0id; 02.03.2015
извините за огромное количество вопросов, но у меня есть еще один вопрос. Полярный угол вершины — это угол, который вектор, идущий от начала координат к вершине, образует с осью x, но я никогда не видел полярный угол вершины относительно другой вершины (точки A в нашем случае). Будет ли это угол между векторами из начала координат в точку и вектором из начала координат в точку А.
- person Andrew Brick; 02.03.2015
Формально точка (x1, y1) меньше точки (x2, y2) тогда и только тогда, когда наклон (y1 − y0) / (x1 − x0) меньше наклона (y2 − y0) / (x2 − х0). оттуда: coursera.cs.princeton.edu/algs4/assignments/collinear.html
- person Everv0id; 02.03.2015
Вы можете легко сделать это в Log(h), используя мой алгоритм, использующий результат промежуточного квадранта. См.: codeproject.com/Articles/ 775753/ и/или (позднее): codeproject.com/Articles/1210225/
- person Eric Ouellet; 22.11.2017
