سال انتشار: ۱۳۸۵

محل انتشار: دوازدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۶

نویسنده(ها):

Ahmad Biniaz – Department of Computer Science and Engineering, College of Engineering, Shiraz University, Shiraz, Iran
Gholamhossein Dastghaibyfar – Department of Computer Science and Engineering, College of Engineering, Shiraz University, Shiraz, Iran

چکیده:

This paper presents a survey as well as a new sweep-circle algorithm, on plane sweep algorithms for computing the Delaunay triangulation. The algorithms examined are: Fortune’s sweep-line algorithm, Zalik’s sweep-line algorithm, and a sweep-circle algorithm proposed by Adam, Kauffmann, Schmitt, and Spehner. We test implementations of these algorithms on a number of uniform and none-uniform distributed sites. We
also analyze the major high-level primitives that algorithms use and do an experimental analysis of how often implementations of these algorithms perform each operation.