$N$ köşeli çokgen

Question

Düzlemde $N$ nokta verilsin. Bu noktalar köşe olacak şekilde kendini kesmeyen bir $N$-gen her zaman çizilebilir mi? 

Bu sorunun yanıtı, noktaların hepsi doğrusal olmadığı sürece, olumlu(ymuş). Bu durumda, bu $N$ noktayı öyle sıraya dizmek istiyoruz ki noktaları sıradan birleştirince çıkan çokgen kendini kesmesin. Nasıl bir yöntemle sıralayabiliriz?

Comments

Bir çokgen çizilebiliyorsa, noktaların konveks hullıyla çokgenin aynı olduğu bariz.Dolayısıyla konveks hullın içinde nokta kalıyorsa soruya cevap HAYIR (örn. (0,1), (0,0), (1,0), (-1,-1) ). Soruyu yanlış mı anlıyorum?
Üstelik 5 nokta bir üçgen belirtebilir. Bu da dejenere bir beşgen olarak görülebilir. Dejenere çokgenlere izin var mı?

---

Dejenere çokgenlere izin var tabii. İlk sorunun yanıtı olumlu, burada var zaten:

http://www.jstor.org/stable/2688993

---

Soruda konvekslik koşulu var sanmıştım. Pardon.

Answer 1

Dogrusal olmadiginda sunlari hesaplayalim. $d(x,y)$ aralarindaki mesave ($x \neq y$). Simdi sirasiyla bunlari sabit $x$ degerleri icin kucukten buyuge siralayalim. ilk iki kucugu alalim, birlestirmek icin.

eger 2 kucuk alamiyorsak, yani mesafeler arasinda esitlik varsa: burda en az 4 nokta oluyor ve biri en az 2yi sagliyor.

Cok geometrik oldu, ispatsiz ama. (ispatlari da, bu ikinci satirin, biraz uzun ve mesakkatli olabilir) Bilgisayar programi azacak olsam bu sekilde yazardim algoritmasini.

Comments

ek olarak ilk once dogrusallari birlestirmeliyiz. yoksa algoritma coker.

---

Ben anlayamadım bu yöntemi. Eğer kolaylaştıracaksa, herhangi üç noktanın aynı doğru üzerinde olmadığı varsayımını yapabiliriz.

---

Daha basit bir yöntem geldi aklıma da, fotoğrafını çekerim ya da bilgisayar olunca yazarım. Şu an tabletten zor :) Bunda biraz sıkıntı var galiba bir de.

---

Sanırım bu minimum spanning tree algoritmasına karşılık geliyor? Her adımda grapha bağlanılabilecek en kısa nodeu bağlıyorsunuz değil mi?

---

Bu soruyu unutmusum.. Sadece kesisimlerden kurtaracak bir algoritma yazmistim ama.. eger iki dogru kesisirse kesisimden kurtulabildigimizi gostersek yeter. Bu nedenle ustte yazdigimda eksiklik var.

Evet, oyle dusundum ama bazen problem oluyor galiba. yani en kisayi dusundugumuzde bazen kesisim olabiliyor. Eger tek eleman icin bakmaksak. En en guzeli herhalde bu kosulu da eklemek, kesisirlerse kesisim ayirma fonksiyonunu kullan. Bu da kolay aslinda.

---

Üstte verdiğiniz algoritmayla bir kesişim olabileceğini zannetmiyorum. Kesişim olan bir örneğiniz var mı?

---

(0,1), (0,0), (1/2,0), (1,0), (1,-1). Bunda kesisiyor galiba.