Menjaga medan dengan dua menara

Abstract

Komputasi geometris merupakan bidang ilmu komputer yang berhubungan dengan komputasi pada benda-benda geometri. Salah satu permasalahan umum pada bidang komputasi geometris adalah Art Gallery Problems. Diberikan denah sebuah museum, ingin dicari jumlah kamera paling minimum yang dibutuhkan untuk melihat seluruh area museum. Salah satu variasi dari Art Gallery Problems adalah masalah Terrain Guarding atau menjaga medan. Medan terbentuk dari titik dan garis yang terhubung sebagai sebuah polyline. Dalam masalah ini, medan memiliki dimensi 1.5 yang berarti polyline tersebut monoton terhadap salah satu sumbu. Dalam kasus ini, sumbu yang monoton adalah sumbu x. Variasi menjaga medan yang ingin diselesaikan adalah menjaga medan dengan menggunakan dua menara yang memiliki tinggi yang sama dan minimal. Pada permasalahan ini, terdapat tiga sub-masalah berdasarkan variasi penempatan kedua menara. Pada kasus diskrit, ingin dicari dua menara yang dasar menaranya terletak tepat di titik pada polyline. Pada kasus kontinu, kedua dasar menara terletak di garis pada polyline. Pada kasus semi-kontinu, salah satu dasar menara terletak di garis dan dasar menara yang lain terletak tepat di titik pada polyline. Algoritma yang akan diimplementasikan untuk menyelesaikan ketiga masalah di atas dibuat oleh Sergei Bespamyatnikh, dkk. Secara umum, algoritma tersebut mencari seluruh kemungkinan posisi dan tinggi menara dengan menggunakan metode bisection. Algoritma tersebut memiliki kompleksitas waktu O(n4) di mana n adalah kompleksitas dari polyline. Untuk kasus semikontinu dan kasus kontinu, kompleksitas waktu algoritma adalah O(n4 + n2f) dan O(n4 + n3f), secara berturut-turut, di mana f adalah waktu yang dibutuhkan untuk perhitungan terkait posisi dan tinggi menara saat menjalankan metode bisection. Perangkat lunak dibuat dengan bahasa pemograman Java. Masukan dari perangkat lunak adalah sebuah file berisi gambar medan yang dibuat dengan aplikasi IPE. Keluaran dari perangkat lunak adalah gambar medan dengan dua menara dengan tinggi yang sama dan minimal. Gambar tersebut dapat dibuka dengan IPE. Hasil implementasi diuji dengan data medan yang tersedia di internet. Pengujian dilakukan dengan medan berbentuk parabola, gelombang sinus, acak dan konkaf. Hasil pengujian diverifikasi secara parsial menggunakan algoritma yang dibuat oleh Agarwal dkk. Hasil verifikasi menunjukkan bahwa tinggi dan lokasi dari menara kedua sudah optimal berdasarkan tinggi dan lokasi dari menara pertama.