Uji Kecepatan Algoritma Convex-Hull: Graham dan Melkman

Abstract

The creating of convex hull for simple polygon is the basic application for computer graphics that can be developed to more complex application. Not all of convex hull algorithms have the same speed and quality, therefore it needs to choose the most appropriate one for our computer graphics application. In this research, two convex hull algorithms will be consider, those are Three Coin's (Graham) and A.A. Melkman's algorithms. Both of them will be compared based on the speed in creating the convex hull. In Three Coins algorithm, we find an extremal point and used bubble sort for its processes, while Melkman algorithm does not used sorting but it uses decque. From the analysis of the program which can be seen from time complexity, it is proved that Three coins algorithm had O(n2) while Melkman algorithm had O(n). From the result of testing repeatedly 25 times, it can be found that the average speed to create convex hull for simple polygon using 50 vertices, Three Coins (Graham) algorithm needs 53,8454 ms, while Melkman algorithm needs 0,116 ms. It means that the Melkman algorithm is faster 464 times than Three Coins (Graham) algorithm to create convex hull for simple polygon. Abstract in Bahasa Indonesia : Pembuatan convex hull pada simple polygon adalah aplikasi dasar pada komputer grafik yang dapat dikembangkan menjadi aplikasi grafik lain yang lebih kompleks. Tidak semua algoritma convex hull pada simple polygon mempunyai kecepatan dan ketepatan yang sama baiknya. Sehingga perlu dipilih yang terbaik dari algoritma - algoritma tersebut. Pada penelitian ini dibandingkan dua algoritma convex hull yaitu algoritma Three Coins (Graham) dan algoritma A.A. Melkman's, sebagai acuannya adalah simple polygon. Kedua algoritma ini akan dibandingkan berdasarkan kecepatan proses dalam pembuatan convex hull. Pada algoritma Three Coins dicari titik ekstrim dan digunakan bubble sort dalam prosesnya sedang pada algoritma Melkman tidak memakai proses sorting namun memakai decque. Hasil analisis program ditinjau dari kompleksitas waktu, didapatkan bahwa untuk algoritma Three Coins (Graham) adalah O(n2) sedangkan algoritma Melkman adalah O (n). Dari hasil pengujian yang diulangi sebanyak dua puluh lima kali, didapatkan bahwa kecepatan rata-rata untuk membuat convex hull untuk simple polygon dengan 50 vertices, menggunakan algoritma Three Coins (Graham) adalah 53.8584 ms sedangkan kalau memakai algoritma Melkman adalah 0,116 ms. Ini berarti algoritma Melkman lebih cepat 464 kali untuk pembuatan convex hull untuk simple polygon dibandingkan dengan algoritma Three Coins (Graham). Kata kunci: convex-hull, simple polygon, Three Coins, Graham, Melkman, kecepatan , komputer grafik.