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(n 2 ) 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).

Creator(s)

• (85-009) Djoni Haryadi Setiabudi
• EDWIN JAYASAPUTRA

Contributor(s)

-

Publisher

Universitas Kristen Petra; 2002

Language

Indonesian

Category

jou – Journal

Sub Category

-

Source

Jurnal Teknik Elektro Vol. 2, No. 1, Maret 2002: 27- 31; Djoni Haryadi Setiabudi (85-009), Edwin Jayasaputra (NA00000365)

Subject(s)

• PROGRAMMING (ELECTRONIC COMPUTER)
• COMPUTER GRAPHICS

File(s)

• jiunkpe-ns-jou-2002-85-009-8466-convex_hull-resource1.pdf