Testowanie, czy zbiór n punktów na płaszczyźnie tworzy wypukły n wielokąta w czasie o (nlogn)

Załóżmy, że otrzymujesz zestaw n punktów na płaszczyźnie i chcesz sprawdzić, czy tworzą one wypukły n wielokąt, tj. Czy wszystkie leżą na wypukłym kadłubie. Zastanawiałem się, czy ktoś wie, jak to zrobić w czasie o (nlogn), tj. Bez obliczania CH.

cg.comp-geom

— Babis Tsourakakis
źródło

Możesz obliczyć wypukły kadłub w czasie O (n log n). Czy masz na myśli, czy można to zrobić w krótszym czasie?

— Per Vognsen,

tak, uważam, że dla tego problemu powinien istnieć algorytm liniowy. ale nie wiem jak

— Babis Tsourakakis

Napisał o (nlogn) nie O (nlogn), więc jego pytanie jest poprawne.

— Shiva Kintali,

Używam małej notacji o, więc pytanie wciąż pozostaje

— aktualne

Trochę zmarszczyłem brwi, widząc sortowanie liczb (lub równo wypukłe kadłuby punktów kartezjańskich) określone jako zabieranie Θ (n log n) czasu bez wyraźnego stwierdzenia, jakiego modelu obliczeń używasz. Sortowanie porównawcze zajmuje Θ (n log n), ale model porównawczy nawet nie pozwala na obliczenie kadłubów. Oba są nadal Θ (n log n) czasem na algebraiczne drzewa decyzyjne (jak pokazuje zaakceptowana odpowiedź), ale są szybsze w modelach obliczeniowych, które bardziej przypominają rzeczywiste komputery.

— David Eppstein

Odpowiedzi:

Wydaje się to mało prawdopodobne, przynajmniej w modelach drzewa porównawczego / algebraicznego. Najpierw definicja:

$P$ $P$ $P$

$n$ $\Omega(n \log n)$ $n$ $X$

P = {(x, x^{2}) | x \in X} .

$P = \{ (x, x^2) | x \in X\}.$

Jeśli istnieje liczba powtarzana, to ta liczba powtórzona odpowiada punktowi, który można zapisać jako wypukłą kombinację pozostałych punktów. Mianowicie punkty nie są w pozycji wypukłej.

Mianowicie, decyzja, czy zbiór punktów znajduje się w pozycji wypukłej, jest tak trudna, jak UNIKALNOŚĆ.

— Sariel Har-Peled
źródło

X [i]

$X[i]$

(X [i], X [i]^{2} + i / n^{2})

$(X[i], X[i]^2+i/n^2)$

@Babis: Redukcja Jeffa działa, gdy duplikaty punktów nie są dozwolone. Punkty generowane przez redukcję są unikalne niezależnie od początkowej tablicy.

— Vinayak Pathak,

W ten sposób otrzymujemy, że liczba narożników wypukłego kadłuba jest równa n wtedy i tylko wtedy, gdy żadne dwa punkty nie mają tej samej współrzędnej x. Wielkie dzięki, początkowo myślałem, że powinno być łatwiejsze niż sortowanie.

— Babis Tsourakakis,

Dzięki Vinayak, nie widziałem redukcji Jeffa, ponieważ została opublikowana w tym samym czasie, gdy pisałem poprzedni komentarz, który zastąpiłem powyższym

— Babis Tsourakakis

Na pewno nie zgadzam się ze zwrotem „model standardowy”. Właśnie tym jest Word RAM :) Jest to model, który najbardziej pasuje do prawdziwego komputera i którego używamy do analizy algorytmu w większości TCS. Geometria zażądała wyjątku, aby używać prawdziwej pamięci RAM, abyśmy nie musieli zajmować się problemami z precyzją. Ale to nie jest „model standardowy”.

— Mihai

-1

$O(n log n)$

Kiedy poznasz kolejność punktów, kąt od każdego punktu do następnego punktu w sekwencji powinien być monotoniczny. To warunek konieczny i, jak sądzę, wystarczający.

Zdobycie punktu wewnętrznego pozostawia się jako ćwiczenie dla czytelnika.

$O(n log n)$

— BCS
źródło

Prawdopodobnie źle odczytałeś jego o (n log n) jako O (n log n) tak samo jak ja. W każdym razie zarysowanym przez ciebie algorytmem jest pakowanie prezentów w formie embrionalnej. W rzeczywistości nie musisz używać punktu wewnętrznego; możesz użyć punktu na granicy, np. punktu o minimalnej współrzędnej x.

— Per Vognsen

O (n l o g n)

$O(n log n)$

o ()

$o()$

Chodzi o to, że istnieje wiele algorytmów wypukłego kadłuba, które działają w O (n log n). Twój algorytm to po prostu stare opakowanie prezentów. Prosił o coś szybszego, np. Czas liniowy. Zobacz inne odpowiedzi.

— Per Vognsen

Jeśli chodzi o edycję, jeśli możesz spojrzeć na zaakceptowaną odpowiedź powyżej swojej, zobaczysz, że problem jest równoważny z wyjątkowością elementu, który ma dolną granicę O (n log n).

— Per Vognsen

@BCS: Obawiam się, że masz jakieś nieporozumienie na temat odpowiedzi Sariel Har-Peled. Redukcja polega na unikalności na wypukłym badaniu położenia, a nie w innym kierunku. Oznacza to, że Sariel (i JeffE) stwierdzili, że jeśli otrzymujesz zestaw liczb i chcesz przetestować unikalność, możesz przekonwertować go na zbiór punktów i użyć dowolnego algorytmu do wypukłego testowania pozycji.

— Tsuyoshi Ito