(Categoria _Structuri de date_, Autor _Cosmin Negruseri_)

h2. Articol scris de 'Blog Fest':https://blogfest.ro/
 
 

h2. Introducere
In acest articol voi discuta despre cateva structuri de date folositoare pentru probleme de geometrie, in special pentru probleme ortogonale. **Problema de baza** ce va fi rezolvata suna in felul urmator: avem $n$ puncte in plan si pentru un anumit dreptunghi ne intereseaza numarul de puncte din acel dreptunghi, sau diverse alte operatii pentru punctele din interiorul sau, cum ar fi suma cheilor punctelor, minimul sau maximul cheilor (daca punctele au asociate cate o cheie). Folosind arbori de intervale putem rezolva aceasta problema, dar vreau sa exemplific ce alte variante mai avem si avantajele lor, precum si aplicatii practice pentru cautarea pe domenii ortogonale. In general, abordarile prezentate mai jos se pot extinde de la cazul unidimensional sau bidimensional, cu usurinta, la cazuri N-dimensionale.

h2. Bibliografie
# 'Arbori de intervale ("segment trees") si aplicatii in Geometria Computationala, Dana Lica':arbori-de-intervale

# 'Arbori Indexati Binar, Mihai Scortaru, GInfo':http://www.ginfo.ro/revista/13_1/focus.pdf

# 'Arbori Indexati Binar, Mihai Scortaru, GInfo':http://www.ginfo.ro/revista/13_1/focus.pdf
# 'Kd-Trees, Andrew W. Moore':http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en

3692