Masalah Geometrik
Pengertian Geometrik
Geometri didefinisikan sebagai cabang matematika yang mempelajari tentang titik garis, bidang dan benda-benda ruang serta sifat-sifatnya, ukuran-ukurannya dan hubungan satu dengan yang lain. Geometri dapat dipandang sebagai suatu studi tentang ruang fisik (Muharti, 1986). Sedangkan tujuan dalam mempelajari geometri menurut Susanta (1996) adalah mengembangkan berpikir secara logis, mengembangkan daya tilik ruang (spatial sense) bagi dunia nyata, sedangkan menurut Clements dan Batista (1990) adalah menunjang mata pelajaran yang lain. Daya titik ruang sangat diperlukan sebagaimana digunakan untuk menafsirkan, memahami, mempelajari dunia geometri dan merupakan salah satu dari kompetensi intelektual manusia. Daya titik ruang sangat penting untuk pemikiran ilmiah dan dapat digunakan untuk memecahkan masalah.
Banyak konsep matematika lebih mudah dipahami jika disajikan dengan bahasa geometri. Untuk dapat mempelajari geometri dengan baik, siswa dituntut untuk menguasai kemampuan dasar geometri, keterampilan dalam membuktikan, keterampilan membuat lukisan dasar geeometri dan mempunyai daya titik ruang yang memadai Susanta (1996). Sedangkan menurut Burger dan Culpepper (1993) Pengajaran geometri melatihkan berpikir secara nalar, juga melatihkan pengenalan struktur.
Kemampuan psikomotor juga dibutuhkan dan digunaka.dalam pembelajaran geometri. Hal ini tampak terlihat jelas padalukisan geometri. Walauptin 1ukisan bukan termasuk obyek geometri karena membicarakan benda-benda konkret yaitu gambar titik (noktah), gambar garis (goresan), dan lingkaran, tetapi lukisan mempunyai nilai pendidikan yang tinggi (Wirasto, 1973). .
Hoffer (Meserve dan Meserve, 1984) mengemukakan lima keterampilan dasar dalam belajar geometri yaitu keterampilan visual, verbal, menggambar, logika dan terapan. Masing-masing keterampilan tidak dapat berdiri sendiri tetapi dalam belajar geometri bersifat komprehensif. Lima keterampilan diantaranya adalah:
A. Keterampilan Visual (K1)
Keterampilan visual meliputi daya untuk: mengenal bermacam bangun datar dan bargun ruang; mengamati bagian-bagian dari sebuah bangun dan keterkaitan bagian satu dengan bagian yang lain; menemutunjukkan pusat simetri, sumbu simetri dan bidang simetri dan gambar sebuah bangun; mengklasifikasi bangun-bangun geometri menurut ciri-ciri yang diamati; mengumupulkan informasi lanjut berdasarkan pengamatan visual; dan mempresentasikan representasi (model) geometri, atau contoh penyangkal, yang menyatakan secara implisit oleh data dalam suatu sistem matematika deduktif.
B. Keterampilan Verbal (K2)
Keterampilan verbal meliputi daya untuk: menemutunjukkan bermacam bangun geometri menurut namanya; memvisualisasikan bangun geometri menurut deskripsi verbalnya; mengungkapkan bangun geometri dan sifat sifatnya; merumuskan definisi yang tepat dan benar; mengungkapkan hubungan antar bangun; mengenali struktur logis dari masalah verbal; dan merumuskan pernyataan generalisasi dan abstraksi.
C. Keterampilan menggambar (K3)
Keetarampilan menggambar meliputi daya untuk: mensketsa gambar bangun dan melabel titik-titik tertentu; mensketsa gambar bangun menurut deskripsi variabelnya; menggambar atau mengkontrusi gambar bangun berdasarkan sifat-sifat yang diberikan; mengkonstruksi gambar bangun yang mempunyai kaitan tertentu dengan gambar-gambar yang diberikan; mensketsa bagian-bagian bidang dan interseksi gambar-gambar bangun yang diberikan; menambahkan unsur-unsur tambahan yang berguna pada sebuah gambar bangun; mengenal peranan (dan keterbatasan) sketsa dan gambar bangun yang terkonstruksi; dan menyeketsa atau mengonstruksi model geometri atau contoh penyangkal.
D. Keterampilan logika (K4)
Keterampilan logika meliputi daya untuk : mengenal perbedaan dan kesamaan antar bangun geometri; mengenal bangun geometri yang dapat diklasifikasikan menurut sifat-sifatnya; menentukan apakah sebuah gambar, masuk atau tidak dalam kelas tertentu;. memahami dan menerapkan sifat-sifat penting dan definisi; menemutunjukkan akibat-akibat logis dari data-data yang diberikan; mengembangkan bukti-bukti yang logis; dan mengenal peranan dan keterbatasan metode deduktif.
E. Kiterampilan terapan (K5)
Keterampilan terapan meliputi daya untuk : mengenal model fisik dan bangun geometri; menyeketsa atau mengonstruksi model gometri bedasakkan objek fisiknya; menerapkan sifat-sifat dan model geometri pada sifat-sifat terkaan dan objek fisik atau himpunan objek fisik; mengembangkan model-model geometri untuk fenomena alam; himpunan elemen di Ilmu Pengetahuan Alam dan himpunan elemen dalam Ilmu Pengetahuan Sosial; dan menerapkan model-model geometri dalam pemecahan masalah.
Permasalahan-permasalahan tidak hanya bersumber dari diri siswa tetapi juga ada faktor yang lain. Sebagaimana diungkapkan Suwarsono (2000) bahwa ada beberapa permasalahan-permasalahan dalam pembelajaran geometri di sekolah. Permasalahan-permasalahan. dalam pembelajaran geometri di sekolah antara lain:
- Masalah materi pelajaran geometri berkaitan erat dengati ditenftkan dala in kurikulum, di setiap jenjang pendidikan.
- Aspek-aspek dan materi pembelajaran geometri meliputi; apa yang sudah materi pelajaran yang ada terlalu padat jika dikaitkan dengan waktu yang kapasitas belajar siswa pada umumnya.
Masalah klasik :
1. Problem closest pair : diberikan titik
pada suatubidang, dan temukan pasangan
terdekatnya
2. Convex hull : temukan poligon cembung
terkecil yang melibatkan smeua titik yang telah ditentukan.
Convex hull adalah masalah klasik ,
dan Persoalannya digambarkan secara
sederhana dalam ruang dimensi dua (bidang) sebagai mencari subset dari himpunan
titik pada bidang tersebut sedemikian rupa sehingga jika titik-titik tersebut
dijadikan poligon maka akan membentuk poligon yang konveks. Suatu poligon
dikatakan konveks jika digambarkan garis yang menghubungkan antar titik maka
tidak ada garis yang memotong garis yang menjadi batas luar poligon. Definisi
lain dari convex hull adalah poligon yang disusun dari subset titik sedemikian
sehingga tidak ada titik dari himpunan awal yang berada di luar poligon
tersebut (semua titik berada di batas luar atau di dalam area yang dilingkupi
oleh poligon tersebut).
Petunjuk untuk menyelesaikan
persoalan ini adalah persamaan garis pada bidang. Persamaan garis pada bidang
memisahkan bidang menjadi dua bagian yaitu area di sebelah kanan bidang
(relatif terhadap orientasi garis). Sebagai contoh garis berorientasi adalah
sumbu koordinat. Misalkan saja sumbu vertikal (ordinat, arah orientasi ke
atas), seluruh titik di sebelah kanan garis ini memiliki nilai komponen
koordinat horizontal (X) yang positif sedangkan seluruh titik di sebelah kiri
garis memiliki nilai komponen koordinat horizontal negatif.
Petunjuk di atas dimanfaatkan dengan
membuat definisi bahwa garis yang dibentuk oleh titik-titik poligon jika
diasumsikan memiliki orientasi yang sama, maka setiap titik berada di sebelah
kanan seluruh garis batas tersebut. Definisi ini kemudian dimanfaatkan untuk
menentukan aksi awal yaitu memilih titik yang berada paling luar pertama.
Mencari titik pertama cukup mudah yaitu cukup memilih titik yang memiliki nilai
komponen koordinat (horizontal atau vertikal) yang ekstrim (minimum atau
maksimum). Titik-titik convex hull lainnya ditentukan berdasarkan titik pertama
tadi.
Algoritma awal yang intuitif dari
deskripsi paragraf sebelumnya adalah :
- memilih titik pertama
- memilih titik berikutnya, berdasarkan definisi:
- jika dibuat garis dengan titik sebelumnya maka seluruh titik lainnya tidak ada yang berada di sebelah kiri.
- jika titik tersebut sesuai maka dimasukkan dalam daftar titik luar.
Algoritma tersebut menggunakan pendekatan exhaustive (brute-force).
kompleksitas algoritma tersebut mendekati O(n2). Algoritma tersebut dapat
dioptimasi dengan membuat agar kumpulan titik-titik tersebut terurut secara
lexicografis (urutkan dulu berdasarkan koordinat sumbu-X lalu untuk koordinat
pada sumbu-X yang sama urutkan berdasarkan koordinat pada sumbu-Y). Sifat
keterurutan ini kemudian dimanfaatkan sehingga pada setiap fase tiap titik
hanya dikunjungi satu kali (kompleksitas linier). Adapun fase-fase yang perlu
dilalui terdiri dari dua fase yaitu batas bagian atas (upper boundary) dan
batas bagian bawah (lower boundary).
Penerapan Algoritma Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer
Pada penyelasaian masalah pencarian Convex Hull dengan
menggunakan algoritma Divide and Conquer, hal ini dapat dipandang
sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini
merupakan garis besar gambaran dari algoritmanya:
Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S
yang diberika berdasarkan koordinat absis-X, dengan kompleksitas
waktu O(n log n).
Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force
dengan kompleksitas waktu O(1). (Basis).
Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan
A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan
koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah
|S| dan titik dengan koordinat absis-X terbesar.
Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB =
conv(B).
Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi
convex hull, H, dengan menghitung da mencari upper dan lower4
tangents untuk HA dan HB dengan mengabaikan semua titik yang berada
diantara dua buah tangen ini.
procedure D_and_C_CH (input P [1..n] : array
of Point, Output L : List of Point)
{ Menyelesaikan masalah convex hull dengan algoritma D-and-C.Masukan: masukan array of point yang berukuran n Keluaran: solusi dari masalah
}
Kamus
r : integer
la : list of point
Algoritma
L = {}
if n ≤ 30 then {ukuran masalah sudah cukup
kecil }
SOLVE upa-masalah dengan metode brute-force
else
Bagi menjadi r upa-masalah, masing-masing
berukuran n/k
HA = P[1..n/2]
HB = P[n/2+1..n]
C_and_D_CH(HA)
C_and_D_CH(HB)
{gabungkan solusi dari r upa-masalah
menjadi solusi masalah semula }
H = prosedur gabung Ha dan Hb dengan
mencari lower tangen dan upper tangen
La = listPoint(H)
L = L ∪ la
Endif