Nauka trójkątów w płaszczyźnie

I przypisany Moi studenci problem znalezienia trójkąt spójne z kolekcją punktów w , oznaczonego . (Trójkąt jest zgodny z próbką oznaczoną, jeśli zawiera wszystkie punkty dodatnie i żaden z punktów ujemnych; z założenia próbka przyjmuje co najmniej 1 spójny trójkąt). $m$ $\mathbb{R}^2$ $\pm1$ $T$ $T$

Najlepsze, co mogliby zrobić (lub ja), to algorytm działający w czasie , gdzie to wielkość próbki. Czy ktoś może zrobić lepiej? $O(m^6)$ $m$

— Aryeh
źródło

Żeby było jasne: wierzchołki trójkąta nie muszą być punktami kolekcji, prawda? Czy dopuszczalne są punkty ujemne na granicy?

— ex0du5

(1) Głosowałem za zamknięciem pytania, ponieważ źle zrozumiałem problem. System nie pozwala mi anulować mojego głosu, ale praktycznie go anuluję. (2) Myślę, że istnieje algorytm czasu O (m log m), ale nie mam czasu, aby go teraz zweryfikować. Chodzi o to, aby obliczyć wypukły kadłub pozytywnych przykładów i omiatać ten wypukły kadłub, aby znaleźć trzy linie tworzące pożądany trójkąt.

— Tsuyoshi Ito

@ ex0du5 - rzeczywiście wierzchołki trójkąta nie muszą składać się z punktów próbnych. Jeśli chodzi o kwestie brzegowe, można je tutaj zignorować, ponieważ są nieistotne. [Jeśli granica liczy się jako część trójkąta, to nie będziesz mieć ujemnych punktów na granicy.]

— Aryeh

@TsuyoshiIto: Myślałem podobnie, ale zdarzają się przypadki, w których krawędzie trójkąta nie mogą być współliniowe z krawędziami wypukłego kadłuba, ale trójkąt nadal istnieje. Trójkąt nadal oczywiście zawiera wypukły kadłub, ale nie tylko rozszerza linie kadłuba i znajduje trójkąt. Możesz potrzebować linii, które są obracane wokół niektórych wierzchołków, aby uniknąć punktów ujemnych. Dlatego zapytałem o negatywy na granicy, aby umożliwić algorytmowi wyszukiwania, który wybrał linie od wierzchołków kadłuba do negatywów, aby zachować dyskretne wyszukiwanie.

— ex0du5

@ ex0du5: Cóż, nie zakładałem, że krawędzie trójkąta są równoległe do niektórych krawędzi wypukłego kadłuba pozytywnych przykładów.

— Tsuyoshi Ito

$O(n\log n)$ $\Omega(n\log n)$

$C$ $q$ $q$ $C$ $C$ $W(q)$ $C$ $F$ $W(q)$ $C$ $F$ $C$ $F$ $O(n\log n)$

przykład $ C $ i $ F $

$F$ $F$ $O(n)$ $F$ $e$ $e$

Zobacz oryginał, aby uzyskać więcej informacji:

Herbert Edelsbrunner i Franco P. Preparata. Minimalna separacja wielokątów . Informacje i obliczenia 77 (3): 218–232, 1988.

— Jeffε
źródło

$T$ $T$

$t$ $A$ $B$ $t$ $BC$ $B$ $C$

$t$

$t$
$A$ $B$ $t'$ $A$ $ABC$ $AB$ $BC$ $A$ $C$
$t'$

$O(m^2)$

— shalabuda
źródło