پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 161 |
| تعداد شماره‌ها | 6,532 |
| تعداد مقالات | 70,501 |
| تعداد مشاهده مقاله | 124,098,946 |
| تعداد دریافت فایل اصل مقاله | 97,206,516 |
Sweep Line Algorithm for Convex Hull Revisited | ||
| Journal of Algorithms and Computation | ||
| مقاله 1، دوره 51، شماره 1، شهریور 2019، صفحه 1-14 اصل مقاله (381.09 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2019.71276 | ||
| نویسنده | ||
| Keivan Borna | ||
| Faculty of Mathematics and Computer Science, Kharazmi University, Tehran, Iran | ||
| چکیده | ||
| Convex hull of some given points is the intersection of all convex sets containing them. It is used as primary structure in many other problems in computational geometry and other areas like image processing, model identification, geographical data systems, and triangular computation of a set of points and so on. Computing the convex hull of a set of point is one of the most fundamental and important problems of computational geometry. In this paper a new algorithm is presented for computing the convex hull of a set of random points in the plane by using a sweep-line strategy. The sweep-line is a horizontal line that is moved from top to bottom on a map of points. Our algorithm is optimal and has time complexity $O(nlogn)$ where $n$ is the size of input. | ||
| کلیدواژه‌ها | ||
| convex hull؛ sweep-line method؛ computational geometry؛ graham scan؛ time complexity؛ Performance | ||
|
آمار تعداد مشاهده مقاله: 578 تعداد دریافت فایل اصل مقاله: 531 |
||