Monoton çokgen - Monotone polygon

Yeşil bir kavşağı, mavi iki kavşağı ve kırmızı üç veya daha fazla kavşağı belirtir. En üstteki iki çokgen L'ye göre tek tonluyken, alttaki ikisi değildir.

İçinde geometri, bir çokgen P uçakta çağrılır monoton düz bir çizgiye göre L, eğer her satır ortogonal ise L kesişir P en fazla iki kez.[1]

Benzer şekilde, bir poligonal zincir C denir monoton düz bir çizgiye göre L, eğer her satır ortogonal ise L kesişir C en çok bir kez.

Birçok pratik amaç için bu tanım, bazı kenarların olduğu durumlara izin verecek şekilde genişletilebilir. P ortogonaldir Lve bir basit çokgen iki noktayı birbirine bağlayan bir çizgi parçası ise monoton olarak adlandırılabilir. P ve ortogonaldir L tamamen ait P.

Terminolojiyi takiben monoton fonksiyonlar, önceki tanım tanımlar çokgenler kesinlikle tek tonlu göre L. "İle ilgili" kısmı, katı / katı olmayan ayrımın çizilmesi için gereklidir: bir poligon, L bir çizgiye göre kesinlikle monotondur L1 -den döndürüldü L yeterince küçük bir açıyla.

Özellikleri

Varsayalım ki L ile çakışıyor xeksen. Daha sonra, monoton bir çokgenin en soldaki ve en sağdaki köşeleri, sınırlarını iki monotonluğa ayırır. poligonal zincirler öyle ki herhangi bir zincirin köşeleri doğal sıralarında geçilirken, X koordinatları tekdüze olarak artan veya azalan. Aslında bu özellik monoton çokgen tanımı için alınabilir ve poligona adını verir.

Bir dışbükey Poligon herhangi bir düz çizgiye göre monotondur ve her düz çizgiye göre monoton olan bir çokgendir dışbükeydir.

Doğrusal bir zaman algoritmasının, belirli bir basit çokgenin monoton olduğu tüm yönleri rapor ettiği bilinmektedir.[2] Basit bir çokgeni iki monoton zincire (muhtemelen farklı yönlerde monoton) ayırmanın tüm yollarını rapor etmek genelleştirildi.[3]

Poligondaki nokta monoton bir çokgene ilişkin sorgular şu şekilde yanıtlanabilir: logaritmik zaman sonra doğrusal zaman ön işleme (en soldaki ve en sağdaki köşeleri bulmak için).[1]

Monoton bir çokgen kolayca üçgenlere ayrılmış doğrusal zamanda.[4]

Düzlemdeki belirli bir nokta kümesi için bir bitonik tur noktaları birleştiren monoton bir çokgendir. En az miktar çevre Sabit bir yöne göre belirli bir nokta kümesi için bitonik tur, polinom zamanı kullanma dinamik program.[5] Böylesine minimal bir bitonik turun basit bir çokgen olduğu kolayca gösterilebilir: yeni turun bitonisitesini korurken bir çift kesişen kenar daha kısa kesişmeyen bir çift ile değiştirilebilir.

Bir çokgeni tek renkli çokgenlere bölme

Basit bir çokgen kolayca olabilir tek renkli çokgenlere bölün içinde Ö(n günlükn) zaman. Bununla birlikte, bir üçgen tek renkli bir çokgen olduğu için, çokgen üçgenleme aslında bir çokgeni tek tonlu olanlara ayırmaktır ve bu, basit çokgenler için gerçekleştirilebilir. Ö(n) zaman.[kaynak belirtilmeli ]

Basit bir çokgeni minimum sayıda tekdüze monoton çokgen halinde kesmek (yani, aynı çizgiye göre monoton), polinom zamanında gerçekleştirilebilir.[6]

Bağlamında hareket planlama kesişmeyen iki monoton çokgen, tek bir öteleme ile ayrılabilir (yani, bir çokgenin ötelemesi vardır, öyle ki ikisi düz bir çizgiyle farklı yarı düzlemlere ayrılır) ve bu ayrılma doğrusal zamanda bulunabilir.[7]

Genellemeler

Süpürülebilir çokgenler

Bir çokgen denir silinebilirdüz bir çizgi, herhangi bir anda poligonal alanla kesişme noktası bir dışbükey küme olacak şekilde tüm çokgen üzerinde sürekli olarak hareket ettirilebilir. Monoton bir çokgen, tarama sırasında yönünü değiştirmeyen bir çizgi ile taranabilir. Bir çokgen kesinlikle taranabilir alanının hiçbir kısmı birden fazla taranmamışsa. Her iki tür süpürülebilirlik ikinci dereceden zamanda tanınır.[8]

3 boyutlu

Çokgen monotonluğunun daha yüksek boyutlara basit ve basit bir genellemesi yoktur.

Bir yaklaşımda, korunan monotonluk özelliği, çizgi L. Üç boyutlu polihedron denir zayıf monoton yönünde L tüm kesitler ortogonal ise L basit çokgenlerdir. Kesitler dışbükey ise, polihedron denir dışbükey anlamda zayıf monoton.[7] Her iki tür de polinom zamanında tanınabilir.[8]

Başka bir yaklaşımda, korunan tek boyutlu özellik ortogonal yöndür. Bu, fikrini doğurur çok yüzlü arazi üç boyutlu: her dikey (yani, Z eksenine paralel) çizginin yüzeyle en fazla bir nokta veya parça ile kesişmesi özelliğine sahip çok yüzlü bir yüzey.

Ayrıca bakınız

Referanslar

  1. ^ a b Preparata, Franco P.; Shamos, Michael Ian (1985), Hesaplamalı Geometri - Giriş, Springer-Verlag, ISBN  0-387-96131-3, 1. baskı:; 2. baskı, düzeltilmiş ve genişletilmiş, 1988:; Rusça çevirisi, 1989:CS1 Maint: ekstra noktalama (bağlantı)
  2. ^ Preparata, Franco P.; Supowit, Kenneth J. (1981), "Basit bir çokgeni monotonluk için test etme", Bilgi İşlem Mektupları, 12 (4): 161–164, doi:10.1016/0020-0190(81)90091-0.
  3. ^ Rappaport, David; Rosenbloom, Arnold (1994), "Kalıplanabilir ve dökülebilir çokgenler", Hesaplamalı Geometri, 4 (4): 219–233, doi:10.1016/0925-7721(94)90020-5.
  4. ^ Fournier, A.; Montuno, D. Y. (1984), "Basit çokgenlerin üçgenlenmesi ve eşdeğer problemler", Grafiklerde ACM İşlemleri, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN  0730-0301, S2CID  33344266
  5. ^ Algoritmalara Giriş, 2. baskı, T. H. Cormen, C. E. Leiserson, R. Rivest, ve C. Stein, MIT Basın, 2001. Problem 15-1, s. 364.
  6. ^ Liu, Robin (1988), "Çokgenlerin tekdüze monoton parçalara ayrıştırılması üzerine", Bilgi İşlem Mektupları, 27 (2): 85–89, doi:10.1016 / 0020-0190 (88) 90097-X.
  7. ^ a b Toussaint, G. T.; El Gindy, H. A. (1984), "İki monoton poligonun doğrusal zamanda ayrılması", Robotica, 2 (4): 215–220, doi:10.1017 / S0263574700008924.
  8. ^ a b Bose, Prosenjit; van Kreveld, Marc (2005), "Tekdüzeliğin genelleştirilmesi: Güzel taramalar hesaplayarak özel çokgen ve çokyüzlü sınıflarını tanıma üzerine", International Journal of Computational Geometry & Applications, 15 (6): 591–608, doi:10.1142 / S0218195905001877, hdl:1874/24150.