Page 223 - E-MODUL PCD 2

konveks jika di seluruh pasangan dua titik yang terkandung di dalamnya dibentuk

oleh garis yang seluruhnya berada dalam S. Dengan demikian, Gambar 11.4(b)

bukanlah bentuk konveks karena garis contoh menghasilkan titik di luar objek.

(a) Himpunan konveks (b) Bukan Himpunan konveks
Gambar 11.4 Konveks dan bukan konveks

Tabel 11.2 Berbagai algoritma convex hull
Algoritma Kinerja Penemu
3
4
Brute Force O(n ) dan O(n ) Tidak diketahui
Graham Scan O(n log n) Graham, 1972
Gift Wrapping O(nh) Jarvis, 1973
QuickHull O(nh) Eddy, 1977
Divide-and-Conquer O(n log n) Preparata & Hong, 1977
Monotone Chain O(n log n) Andrew, 1979
Incremental O(n log n) Kallay, 1984
Marriage- O(n log h) Kirkpatrick & Seidel,
beforeConquest 1986

Dasar untuk memperoleh convex hull pada algoritma Graham Scan dibagi

menjadi tiga tahap.

1. Perolehan titik p0 di dalam himpunan P yang berisi kumpulan titik. Titik p0

ini biasa disebut sebagai titik jangkar atau pivot. Caranya adalah dengan
mencari titik yang mempunyai nilai ordinat Y terkecil. seandainya terdapat

beberapa nilai Y yang memenuhi hal itu, dicari nilai X yang paling kecil.
2. Penghitungan sudut semua titik di dalam P, selain p0 terhadap p0.

Kemudian, semua titik di dalam P selain p0 diurutkan secara radial

berlawanan dengan arah jarum jam.

223