> Struktura danych, która pozwoli ci w czasie stałym dowiedzieć się o
sąsiadach.
> Np. mógłbyś mieć listę wierzchołków, a trójkąty opisywać indeksami do tej
> listy.

To mam, na wejściu dostaję trzy tablice: wierzchołków, trójkątów w
postaci 3 kolejnych indeksów wierzchołków, normalnych wierzchołków.

> Natomiast każdy wierzchołek miałby jeszcze listę trójkątów do których
> należy. Wtedy stwierdzenie, które trójkąty mają wspólne wierzchołki byłoby
> szybkie.

Jakbym to dostawał za free, to tak :-) Większość razy liczę obwiednię
dla nowego zestawu tablic, a cachowanie wszystkiego w pamięci też nie
wchodzi w grę. Ale dzięki za pomysł, pogłówkuję.

> Ad 2. Możesz posortować trójkąty ze względu na normalną, wtedy masz O(nlgn),
> albo nawet wrzucić do tablicy mieszającej: O(1) oczekiwany.

Też zawsze jakiś zysk.

--
Pozdrawiam,
Mateusz Bogusz