[MD-sorular] FW: daha basit bir soru

[Kerem Altun]

Yazdiginizi tam anlayamadim aslinda. Ama sanirim ben sorunu tam
anlatamamisim, bir toparlamaya calisayim:

Bir noktalar kumemiz var, N elemanli, ve uzerinde bir siralama tanimi yok.
Yani harita falan bilmiyoruz aslinda, elimizde olan sadece N noktanin
koordinatlarindan olusan bir kume. Ama bildigimiz soyle bir ozelligi var bu
kumenin, daha dogrusu bu simdilik bir varsayim: bu noktalari kose kabul eden
ve kendini kesmeyen bir cokgen vardir.

Bu varsayim muhtemelen herhangi N nokta icin dogru aslinda, bilmiyorum,
kanitlayamadim ama karsiornek de bulamadim. Hatta birden cok kendini
kesmeyen cokgen vardir muhtemelen.

Biz bunlarin bir tanesini ariyoruz: bu noktalari cizdigimizde gozumuzle
gordugumuz cokgeni. Herhangi N nokta icin bunu gozumuzle goremeyiz belki,
ama bu harita orneginde goruyoruz. Yani belki buyutecle baksak
goremeyecegiz, ya da birden cok cokgen gorecegiz, ondan da emin degilim.
Bilgisayarin da bizim gordugumuz cokgeni gormesini istiyoruz. Tabii
bilgisayarin bunu yapmasinin yolu da, noktalari uygun bir sekilde siraya
dizmek. Benim aklima baska bir yol gelmedi.

Zaten sorun burada basliyor, o noktalar kumesine bakinca gordugumuz seyin
(yani sezgisel olarak yaptigimiz siralamanin) ozelliklerini bulmak gerek ki
bilgisayara da bunu anlatabilelim.

Kerem

2008/10/8 Fatih Gürses <yahyagurses at hotmail.com>

>
> Kerem bey, matematikçiler soruyu basit özel halde çözerek genel haldeki
> çözüm hakkında fikir edinmeye çalışırlar.bu sebepten korkmayınız,yavaş yavaş
> çözüm belirecektir.tabii sizin yardımınız ile.
>
> ekte gönderdiğiniz harita için de geçerli bu algoritma yalınız basit bir
> eklenti gerekiyor ki bu eklenti şudur: *poligonun(P) köşeleri 1 numaralı
> adımda verilen noktalar olmaya da bilir aksi taktirde verdiğiniz harita(H)
> örneği için problem çözümsüzdür. poligon haritanın dışında kalmayacak
> şekilde ona yeni köşeler ekleyebiliriz*.o da şöyle olacak.her adımda bir
> denetleyici koyacağız.denetleyici 1 numaralı adımda
> verilen  z(n),z(n+1) noktalarını aşağıdaki(önceki maildaki) algoritmaya göre
> birleştiren doğru parçasının H nin alt kümesi olup olmadığını
> denetleyecek.eğer bu doğru parçası ki P nin kenarıdır eğer H nin alt kümesi
> ise ne ala,yok eğer değilse (H nin sınırı)∂H den  öyle bir z*(p(n))
> noktası alırız ki argz(n)>argz*(p(n))>argz(n+1) olacak.eğer z(n) ile z*(p(n)) yi
> birleştiren doğru parçası ve z*(p(n)) ile z(n+1) yi birleştiren doğru
> parçalarının ikisi de H içinde ise ne ala,yok eğer her ikisi aynı anda alt
> küme olma şartını sağlamıyorsa o zaman ∂H den öyle iki adet nokta alırız
> ki bunların argümanları yine sıra ile z(n),z(n+1) arasında kalacaktır ve
> imdi bunları ardışık birleştiren üç doğru parçasının H nin alt kümesi olması
> halinde ne ala,yok eğer yine H nin alt kümesi olmuyorsa bu
> algoritma böylece devam eder.
>
> sizin benim evvel sunduÄŸum algoritmaya verdiÄŸiniz counter-example haritada
> kuyruğa benzer kısımda bir nokta aldığınız taktirde saat yönünde noktaların
> birleştirilmesi şartı da yukarıda yaptığım yamayı etkisiz bırakıyor zira
> küme konveks değil.dolayısıyla problem bence well-defined değil.yani şimdi
> yukarıda altı çizili şarta bir de *saat yönünün gerek şart olmadığ*ını
> eklememiz gerekecek.eğer bu problemin yer aldığı bir kaynağa bizi
> sevkederseniz,problemi iyi tanımlı hale getirmek için zaman kaybetmekten
> kurtulmuş ve problemle uğraşmış olacağız.
>
> muhabbetle...
>
>
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20081008/0f32e0fa/attachment.htm