21 października 2022

Obwiednia wypukła jako punkt wyjścia innych algorytmów.

 Od paru dni rozmyślam nad obwiednią wypukłą, szykując się do projektowania matematyki. Podejście jest następujące. Obliczam punkty obwiedni wypukłej. Oddzielam je od innych. Generuję kolejną obwiednię wypukłą, i znów oddzielam jej punkty. Mam teraz dwa wielokąty wypukłe, jeden wewnątrz drugiego. Reszta punktów w środku, czeka na kolejną iterację.

I to moze być punkt startowy kilku wielomianów: np. triangulacji, cyklu Hamiltona, a nawet problemu komiwojażera w przypadku wagi będącej odległością euklidesową, gdyż szukanie najkrótszej trasy degeneruje się do lokalnego przeszukiwania spośród kilku punktów. Wystarczy wybrać sąsiednie bliskie sobie punkty obu obwiedni (przy komiwojażerze może być konieczny jeszcze jeden punkt z bardziej zewnętrznej obwiedni, sąsiad na powstającym cyklu Hamiltona, gdyż odcinek utworzony z dwu sąsiadujących punktów przekształcamy w wielokąt minimalizujący długość ścieżki).