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