Ok, evo trivijalno potpitanje, da vidim sta propustam:

Elem, zar nije prirodnije/najprostije, kad si vec i sam pomenuo oprugu, da se uzme pravi potencijal opruge, tj koji je i privlacan i odbojan, tj:

V(x_i,y_i) = \sum_edge const_1 (L_edge - const_2)^{^2}

gde const_2 ocito ima fizicki smisao ravnotezne duzine opruge? To, bar kao formula, deluje prostije (i zadrzis se na nivou edge-ova) - je li ima neki argument kako vidis da je je to losije resenje?

Poz!

Ovo je vise problem iz fizike nego iz programiranja, ali eto sad...

Metod za crtanje simplicijalnog kompleksa na ekranu bazira se na odredjivanju koordinata za vertekse u globalnom Euklidskom prostoru u koji se embed-uje dati kompleks. Koordinate se odredjuju tako sto se verteksi kompleksa tretiraju kao cestice sa nekim interakcijama u nekom potencijalu, i onda algoritam iterativno aproksimira polozaje cestica koje odgovaraju minimumu tog potencijala.

Drugim recima, npr. za slucaj 2D triangulacija i embed-ovanja u ravni R^2, treba osmisliti izraz za potencijalnu energiju N-cesticnog sistema V(x_i,y_i), gde i=1,...,N, koji ce da stavi cestice u neki ravnotezni polozaj. Jedan predlog koji mi je pao na pamet je da stavimo dvocesticu privlacnu interakciju (oprugu) na svaki edge u kompleksu, i trocesticnu odbojnu interakciju (naduvani balon) u svaki trougao, otprilike ovako:

   V(x_i,y_i) = \sum_edge const_1 (L_edge)^2 + \sum_triangle const_2 / A_triangle,

gde je L_edge(x,y) duzina edge-a izmedju date dve cestice, dok je A_triangle(x,y) povrsina kruga upisanog u trougao sa date tri cestice. Prvi clan je minimalan kada je rastojanje nula, tj. kada sve cestice kolapsiraju u jednu tacku. Drugi clan je minimalan kada su povrsine upisanih krugova beskonacne, pa samim tim i rastojanja izmedju cestica. Kada imamo oba clana, intuicija je da potencijal ima minimum za neku konfiguraciju "izmedju" ova dva granicna slucaja (ako su obe konstante interakcija pozitivne).

Zadatak je dakle sledeci --- ispitati da li N cestica sa ovakvim interakcijama uvek imaju ravnotezno stanje, tj. da li ovaj potencijal ima globalni izolovani minimum za neke vrednosti koordinata x_i,y_i, za svako N. Takodje, razmislite koji drugi mehanicki sistem bi zgodno radio ovaj posao (tako da se cestice nikad ne sudaraju), tj. osmislite i predlozite jos neki, drugaciji predlog potencijala --- sve sile i interakcije su dozvoljene (gravitacija, elektrostatika, opruge, zice, lopte i baloni, ovo, ono, stagod vam padne na pamet). Samo budite sigurni da postoji globalni minimum za konacne vrednosti svih koordinata. Bonus poeni ako potencijal moze lako da se uopsti sa ravni R^2 na n-dim Euklidski prostor R^n, i ako ima mali broj kapling-konstanti.

Btw, ovo mozda moze da se nacrta u Mathematici za neki jednostavan izbor grafa, da vidimo kako bi izgledali polozaji tih cestica ili sl. Recimo, za 4 cestice na grafu sa dva trougla spojena duz jedne ivice, ovako napamet mi se cini da ce gornji potencijal da rasporedi cestice u dva jednakostranicna trougla. Ali za komplikovaniji izbor grafa nisam siguran da postoji minimum, i nisam siguran da je jednoznacan --- gornji potencijal cak ima translacionu i rotacionu invarijantnost, kojih bi takodje trebalo da se otarasimo nekim globalnim spoljasnjim poljem koje ce da narusi te simetrije. Npr ako stavimo sve u neku fiksiranu potencijalnu jamu ili nesto...

Razmislite pa javite, sve ideje i predlozi su dobrodosli. ;-)

:-)
Marko


Dr. Marko Vojinovic
Group for Gravitation, Particles and Fields
Institute of Physics
University of Belgrade
======================
home page: www.markovojinovic.com
e-mail:    vmarko@ipb.ac.rs