ΑΛΓΟΡΙΘΜΟΣ

VAN KREVELD

Ο αλγόριθμος του

Van Kreveld

•

Χρησιμο

ποιεί μια ημιευθεία που αρχίζει από το κελί

που βρίσκεται ο παρατηρητής (o) και περιστρέφεται
αντίστροφα α

πό την φορά του ρολογιού.

•

Κάθε κελί

που τέμνει η ημιευθεία εισάγεται σε ένα

δυαδικό δέντρο

, βάσει της απόστασης του κελιού από

τον

παρατηρητή.

•

Το δέντρο ε

παυξάνεται ώστε κάθε κόμβος του

δέντρου να συγκρατεί το μέγιστο ύψος των

παιδιών

του

.

Χρήστος Μιχαήλ

9