Terrain visibility and guarding problems

Gözetleme kuleleri yangınları tespit edebilmek için arazi üstüne konumlandırılır, askeri birlikler sızmayı önleyebilmek maksadıyla araziyi gözetlemek için tertiplenirler ve röle istasyonları kesintisiz iletişimi sağlamak maksadıyla arazi üzerinde ölü bölge kalmayacak şekilde yerleştirilir. Bu tezde, bir arazi bölümünü veya arazi üzerindeki bir nesneyi algılama veya gözetleme kabiliyetine sahip herhangi bir varlık muhafız olarak adlandırılmıştır. Bu anlamda, gözetleme kuleleri, askeri birlikler ve röle istasyonları birer muhafızdır, ve sensörler, gözcüler (insanlar), kameralar ve benzeri varlıklar da muhafız olarak kabul edilmektedir. Gözetleme, görme, kapsama ve koruma aynı anlamda kullanılmıştır. Belirli bir muhafızın görüş alanı muhafızın arazi üzerinde gördüğü kısımlar olarak tanımlanmış, ve görüş alanı hesaplaması görüş alanı problemi olarak adlandırılmıştır. Arazi üzerindeki her bir nokta en az bir muhafız tarafından korunacak şekilde arazi üzerine en az sayıda muhafız yerleştirme arazi koruma problemi olarak nitelendirilmektedir. Araziler genellikle düzenli kare grid veya düzensiz üçgen ağı şeklinde temsil edilirler. Bu tezde, arazi koruma problemi ve görüş alanı problemini her iki temsil için de ele almaktayız. İlk ele aldığımız problem 1.5 boyutlu arazi koruma problemidir. 1.5 boyutlu arazi düzensiz üçgen ağın bir kesitidir ve parçalı doğrusal bir eğri ile karakterize edilir. Problemin NP-Zor olduğu gösterilmiştir. Problemi optimal çözebilmek için, O(n2) boyutlu bir sonlu egemen küme ve O(n2) boyutlu bir tanık küme sunulmuştur - n arazi üzerindeki köşelerin sayısını ifade etmektedir. Sonlu egemen küme, muhtemelen sayılamayan bir çözüm kümesi olan bir optimizasyon probleminde, optimal bir çözümü ihtiva eden sonlu noktalar kümesidir. Bir tanık kümesi arazinin ayrıklaştırılmasından elde edilen sonlu bir küme olup tanık kümesinin elemanlarının kapsanması arazinin de kapsanması anlamına gelmektedir. Konveks noktalar ve çukur noktalarından oluşan O(n) boyutlu bir sonlu egemen küme olduğunu gösteriyoruz. Aynı zamanda, daha önce bulunan O(n2) boyutlu tanık kümesinden daha küçük O(n) boyutlu tanık kümeleri olduğunu ispat ediyoruz. Daha küçük boyutlu sonlu egemen küme ve tanık kümelerinin sayesinde problemin sıfır-bir tamsayılı programlanmasında kullanılan karar değişkenleri ve kısıtların sayısında azalma meydana gelmektedir. Daha sonra, düzensiz üçgen ağlarda görüş alanı problemi ve arazi koruma problemini, 2.5 boyutlu arazi koruma problemi olarak da adlandırılır, ele alıyoruz. Bu problem için henüz bir sonlu egemen küme ortaya konmamıştır. Ayrıca, problemi optimal çözebilmek için görüş alanı probleminin de çözülmesi zorunludur. Görüş alanı problemini çözmeye yönelik saklı yüzey ayıklama algoritmaları analitik çözümler ortaya koymamakta ve uygulama konusunda belirsizlikler ihtiva etmektedir. Arazinin ufuk çizgisinden faydalanan diğer çalışmalar görüş alanını hesaplarken ufuk çizgisindeki köşelerin ilgili üçgenin bulunduğu düzlemin üstündeki projeksiyonunu bulurlar ve üçgenin üzerindeki görünür alanı bulmak için bu projeksiyonları birleştirirler. Biz bu yaklaşımın hatalı olduğunu gösterdikten sonra üç boyutlu uzayda alternatif bir projeksiyon modeli ortaya koyuyoruz. Başka bir üçgenden dolayı bir üçgen üzerinde meydana gelen görünmez bölgenin doğrusal olmayan denklemlerle ifade edildiği gösterildikten sonra doğrusal olmayan denklemler doğrusallaştırılarak çok düzlemli bir küme elde edildiği ortaya konmaktadır. Son olarak, düzenli kare grid ile yakınsaması yapılan engebeli coğrafi bir arazi parçasının termal kameralar tarafından gözetlenmesini içeren arazi koruma probleminin gerçek bir örneği ele alınmıştır. Düzenli kare gridde arazi koruma problemi ile ilgili konular ortaya konarak problemin çözümüne yönelik tamsayılı programlama modelleri sunulmuştur. Müteakiben, arazinin çözünürlüğünün ve arazi özelliklerinin kapsama optimizasyonu üzerindeki etkisini görebilmek maksadıyla iki hayali arazinin yaratıldığı bir duyarlılık analizi yapılmıştır. Aynı zamanda, engelleyici patika problemi adını verdiğimiz yeni bir problemi tanıttıktan sonra ağ modeline dayalı bir tamsayılı programlama formülasyonu ile problemin çözümü verilmektedir.