Marta Fort, Toni Sellarès (contacta)

EINF, ETIG, ETIS

Considerem un conjunt S de punts d’un mapa on hi ha localitzats serveis d’un determinat tipus, per exemple bombers, ambulàncies, restaurants que porten menjar a domicili, etc. Cada punt s del conjunt S té associada una funció que proporciona el temps total que es tarda a arribar des de s a una posició qualsevol p del mapa. Aquest temps es calcula tenint en compte el que tarda a  arrancar el vehicle que fa el servei des de que es rep un avís, la distància entre s i el punt p, i la velocitat a la que es mou el vehicle.

La regió de Voronoi V(s) del punt s està formada per totes les posicions del mapa per a les quals el temps total d’espera quan es fa un avís  al servei localitzat a s és menor que el  temps total d’espera quan l’avís es fa  a qualsevol dels altres serveis localitzats a punts de S diferents de s.  El diagrama de Voronoi de S, V(S), és la unió de les regions de Voronoi v(s) de tots els serveis de S. Una vegada calculat el diagrama de Voronoi V(S), donada una posició del mapa des de la qual es fa un avís és fàcil determinar el punt de S des del qual es rebrà el servei amb un menor temps d’espera.

L’objectiu del projecte és el disseny d’una aplicació que: a) dibuixi el diagrama de Voronoi V(S) d’un conjunts de punts S; b) permeti consultar per a qualsevol posició del mapa el punt de S des del qual el servei es farà de manera més ràpida.

El projecte es programarà en C++ i en un llengutage de programació de targetes gràfiques (Cg o OpenCl).
Serà convenient tenir o estar disposat a adquirir coneixements d’Informàtica Gràfica.

novembre de 2010