Hatların düzenlenmesi - Arrangement of lines

Basit bir çizgi düzenlemesi (solda) ve basit bir çizgi düzenlemesi (sağda).

İçinde geometri bir hatların düzenlenmesi ... bölüm of uçak bir koleksiyon tarafından oluşturulmuştur çizgiler. Düzenlemelerin karmaşıklığına ilişkin sınırlar, ayrık geometri, ve hesaplamalı geometriler düzenlemelerin verimli bir şekilde inşa edilmesi için algoritmalar bulmuşlardır.

Tanım

Herhangi bir set için Bir satırların Öklid düzlemi biri bir tanımlayabilir denklik ilişkisi hangi iki noktaya göre uçağın noktalarında p ve q eşdeğerdir, her satır için l nın-nin Birya p ve q ikiside l veya her ikisi de aynı açıklığa ait yarım düzlem ile sınırlı l. Ne zaman Bir sonlu veya yerel olarak sonlu[1] denklik sınıfları Bu ilişkinin üç türü vardır:

  1. sınırlı veya sınırsız dışbükey çokgenlerin iç kısımları ( hücreler düzenlemenin), bağlı bileşenler herhangi bir satırında yer almayan düzlemin alt kümesinin Bir,
  2. açık çizgi parçaları ve açık sonsuz ışınlar ( kenarlar Düzenlemenin), başka herhangi bir satıra ait olmayan tek bir çizginin noktalarının bağlantılı bileşenleri Bir, ve
  3. tek noktalar ( köşeler düzenlemenin), iki veya daha fazla çizginin kesişimleri Bir.

Bu üç tür nesne birbirine bağlanarak bir hücre kompleksi uçağı kapsayan. İki düzenleme olduğu söyleniyor izomorf veya kombinatoryal olarak eşdeğer ilişkili hücre komplekslerindeki nesneler arasında bire bir bitişik koruyan bir yazışma varsa.[2]

Düzenlemelerin karmaşıklığı

Düzenlemeler çalışması başladı Jakob Steiner, bir düzenlemenin sahip olabileceği farklı türlerdeki maksimum özellik sayısının ilk sınırlarını kanıtlayan kişi.[3]İle bir düzenleme n çizgiler en fazla n(n − 1)/2 köşeler, geçiş çizgileri çifti başına bir. Bu maksimum elde edilir basit düzenlemeler, her iki çizginin farklı bir çift kesişme noktasına sahip olduğu satırlar. Herhangi bir düzenlemede olacak n sonsuz aşağı doğru ışınlar, satır başına bir; bu ışınlar ayrı n Aşağı yönde sınırsız olan düzenlemenin + 1 hücreleri. Kalan hücrelerin hepsinin benzersiz bir en alt köşesi vardır,[4] ve her köşe, benzersiz bir hücre için en alttadır, bu nedenle bir düzenlemedeki hücre sayısı, köşelerin sayısı artı n + 1 veya en fazla n(n +1) / 2 + 1; görmek tembel ikramcı dizisi. Düzenlemenin kenar sayısı en fazla n2veya kullanılarak görülebileceği gibi Euler karakteristiği köşe ve hücre sayısından veya her bir çizginin en fazla bölündüğünü gözlemleyerek hesaplamak için n diğerinin kenarları n - 1 satır; Yine, bu en kötü durum sınırı, basit düzenlemeler için elde edilir.

bölge bir çizginin l bir çizgi düzenlemesinde, kenarlara sahip hücrelerin toplanmasıdır. l. bölge teoremi tek bir bölgenin hücrelerindeki toplam kenar sayısının doğrusal olduğunu belirtir. Daha doğrusu, çizginin tek bir tarafına ait hücrelerin toplam kenar sayısı l en fazla 5n − 1,[5] ve her iki tarafa ait hücrelerin toplam kenar sayısı l en fazla .[6] Daha genel olarak, herhangi bir dışbükey eğri ile kesişen bir çizgi düzenlemesinin hücrelerinin toplam karmaşıklığı O (n α (n)), burada α, ters Ackermann işlevi kullanılarak gösterilebileceği gibi Davenport-Schinzel dizileri.[6] Tüm bölgelerin karmaşıklıkları toplandığında, bir düzenlemedeki hücre karmaşıklıklarının karelerinin toplamının O (n2).[7]

k düzeyi bir düzenlemenin tam olarak sahip olduğu kenarların oluşturduğu poligonal zincirdir. k doğrudan altlarındaki diğer çizgiler ve ≤k düzeyi düzenlemenin altındaki kısımdır k-seviye. Bir karmaşıklık için eşleşen üst ve alt sınırları bulma k-level, ayrık geometride önemli bir açık problem olmaya devam etmektedir; en iyi üst sınır O (nk1/3), en iyi alt sınır ise Ω (n tecrübe(c (günlükk)1/2)).[8] Buna karşılık, ≤'nin maksimum karmaşıklığık-düzeyi Θ (nk).[9] Bir k-level, bir düzenlemedeki monoton yolun özel bir durumudur; başka bir deyişle, herhangi bir dikey çizgiyi tek bir noktada kesen bir dizi kenar. Bununla birlikte, monoton yollar, çok daha karmaşık olabilir. k-düzeyler: yolun yön değiştirdiği noktaların sayısının Ω olduğu bu düzenlemelerde düzenlemeler ve monoton yollar vardır (n2 - o (1)).[10]

Bir düzenlemedeki tek bir hücre, tümü tarafından sınırlanmış olsa da n hatlar, genel olarak mümkün değildir m tümünün sınırlandırılması için farklı hücreler n çizgiler. Aksine, toplam karmaşıklığı m hücreler en fazla Θ (m2/3n2/3 + n),[11] neredeyse aynı sınır Szemerédi – Trotter teoremi düzlemdeki nokta-çizgi olaylarında. Bunun basit bir kanıtı aşağıdaki gibidir: geçiş sayısı eşitsizliği:[12] Eğer m hücrelerde toplam x + n kenarlar, bir grafik oluşturabilir m düğümler (hücre başına bir) ve x kenarlar (aynı satırdaki ardışık hücre çifti başına bir). Bu grafiğin kenarları, uç noktalarına karşılık gelen hücrelerin içinde kesişmeyen eğriler olarak çizilebilir ve ardından düzenlemenin çizgilerini takip edebilir; bu nedenle, O (n2) bu çizimdeki geçişler. Bununla birlikte, çapraz sayı eşitsizliğine göre, Ω (x3/m2) geçişler; her iki sınırı da karşılamak için, x O olmalı (m2/3n2/3).[13]

Projektif düzenlemeler ve projektif ikilik

Çizgi düzenlemelerini Öklid düzleminde değil de projektif düzlem projektif geometride her çizgi çiftinin bir kesişme noktasına sahip olması nedeniyle. Yansıtmalı düzlemde, düzenlemeleri artık çizgilerin kenarlarını kullanarak tanımlayamayabiliriz (yansıtmalı düzlemdeki bir çizgi, düzlemi iki ayrı kenara ayırmaz), ancak yine de bir düzenlemenin hücrelerini, nesnenin bağlantılı bileşenleri olarak tanımlayabiliriz. herhangi bir çizgiye ait olmayan noktalar, tek bir çizgiye ait nokta kümelerinin bağlantılı bileşenleri olacak kenarlar ve iki veya daha fazla çizginin kesiştiği noktalar olacak köşeler. Yansıtmalı düzlemdeki bir çizgi düzenlemesi, bir çizginin her iki ucundaki iki Öklid ışınının, o çizgideki en soldaki ve en sağdaki köşeleri birbirine bağlayan yansıtmalı düzlemde tek bir kenarla değiştirilmesiyle Öklid'deki karşılığından farklıdır ve bu çiftlerde Sınırsız Öklid hücreleri, yansıtmalı düzlemde sonsuzda yansıtmalı çizgiyle çaprazlanan tek hücreler ile değiştirilir.

Nedeniyle yansıtmalı ikilik Düzlemdeki noktaların kombinatoryal özellikleri hakkındaki birçok ifade, doğruların düzenlenmesiyle ilgili eşdeğer ikili formda daha kolay anlaşılabilir. Örneğin, Sylvester-Gallai teoremi, düzlemdeki doğrusal olmayan herhangi bir nokta kümesinin bir sıradan çizgi tam olarak iki nokta içeren, yansıtmalı dualite altında birden fazla tepe noktasına sahip herhangi bir çizgi düzenlemesinin bir sıradan nokta, yalnızca iki çizginin kesiştiği bir tepe noktası. Sylvester-Gallai teoreminin bilinen en eski kanıtı, Melchior (1940), kullanır Euler karakteristiği böyle bir tepe noktasının her zaman var olması gerektiğini göstermek için.

Düzenlemelerde üçgenler

Kobon üçgenleri 17 satırlık bir düzenlemede

Projektif düzlemde bir çizgi düzenlemesi olduğu söylenir. basit düzenlemenin her hücresi tam olarak üç kenarla sınırlanmışsa; basit düzenlemeler ilk olarak Melchior tarafından incelenmiştir.[14] Basit hat düzenlemelerinin üç sonsuz ailesi bilinmektedir:

  1. Bir yakın kalem oluşan n - Tek noktadan 1 çizgi, aynı noktadan geçmeyen tek ek çizgi ile birlikte,
  2. Birin kenarlarının oluşturduğu çizgiler ailesi normal çokgen onunla birlikte simetri eksenleri, ve
  3. Düzgün bir çokgenin, sonsuzluktaki çizgi ile birlikte yanları ve simetri eksenleri.

Ek olarak birçok başka örnek vardır düzensiz basit düzenlemeler bilinen herhangi bir sonsuz aileye uymayan.[15]Grünbaum olarak[16] yazıyor, basit düzenlemeler "kombinatoryal geometri ve uygulamalarının birçok bağlamında örnekler veya karşı örnekler olarak görünür." Örneğin, Artés, Grünbaum ve Llibre (1998) basit düzenlemeleri kullanarak, bir kümenin derecesi arasındaki ilişkiye dair bir varsayıma karşı örnekler oluşturmak için diferansiyel denklemler ve denklemlerin sahip olabileceği değişmez çizgilerin sayısı. Bilinen iki karşı örnek Dirac – Motzkin varsayımı (hangisi olduğunu belirtir n- satır düzenlemesi en az n/ 2 sıradan nokta) hem basittir.[17]

ikili grafik Hücre başına bir düğüm ve düzenlemenin bir kenarını paylaşan herhangi bir hücre çiftini birbirine bağlayan bir kenarın olduğu bir çizgi düzenlemesi, kısmi küp, düğümlerin etiketlenebileceği bir grafik bitvektörler grafik mesafesi şuna eşit olacak şekilde Hamming mesafesi etiketler arasında; bir çizgi düzenlemesi durumunda, etiketlemenin her bir koordinatı, hatlardan birinin bir tarafındaki düğümlere 0'ı ve diğer taraftaki düğümlere 1'i atar.[18] Sonsuz aileleri oluşturmak için basit düzenlemelerin ikili grafikleri kullanılmıştır. 3-normal kısmi küpler, grafiklerine izomorfik basit zonohedra.[19]

Ayrıca, çok basit olmayan düzenlemelerde üçgen hücrelerin aşırı sayılarını incelemek de ilgi çekicidir. Herhangi bir düzenlemede en azından olmalıdır n üçgenler; sadece sahip olan her düzenleme n üçgenler basit olmalıdır.[20] Basit bir düzenlemede mümkün olan maksimum üçgen sayısının üst sınırlarla sınırlandığı bilinmektedir. n(n - 1) / 3 ve alt sınırı n(n - 3) / 3; alt sınır, normal bir 2'nin köşegenlerinin belirli alt kümeleri ile elde edilir.n-gen.[21] Basit olmayan düzenlemeler için maksimum üçgen sayısı benzerdir ancak daha sıkı sınırlıdır.[22] Yakından ilgili Kobon üçgeni sorunu Öklid düzlemindeki bir düzenlemede üst üste binmeyen sonlu üçgenlerin (yüzleri olması gerekmez) maksimum sayısını sorar; bazıları için ama hepsi için değil n, n(n - 2) / 3 üçgen mümkündür.

Multigrids ve Penrose döşemeleri

ikiye bölünmüş altıgen döşeme.

Basit bir çizgi düzenlemesinin ikili grafiği, geometrik olarak bir koleksiyon olarak temsil edilebilir. rhombi, bu tepe noktasında birleşen çizgilere dik kenarlarla düzenlemenin tepe noktası başına bir tane. Bu eşkenar dörtgen, bir döşeme oluşturmak için bir araya getirilebilir. dışbükey Poligon Sonlu sayıda çizgiden oluşan bir düzenleme durumunda veya sonsuz sayıda çizgiye sahip yerel olarak sonlu bir düzenleme durumunda tüm düzlemde. de Bruijn (1981) Hat düzenlemesinin oluştuğu bu yapının özel durumlarının araştırılması k eşit aralıklı paralel çizgiler kümeleri. İki dikey paralel çizgi ailesi için bu yapı sadece tanıdık kare döşeme düzlemde ve birbirinden 120 derecelik açılarda üç çizgi ailesi için (kendileri bir üç altıgen döşeme ) bu, eşkenar dörtgen döşeme. Bununla birlikte, daha fazla hat ailesi için bu yapı, periyodik olmayan döşemeler. Özellikle, birbirine eşit açıdaki beş çizgi ailesi için (veya de Bruijn'in dediği gibi bu düzenleme, bir Pentagrid) eşkenar dörtgen versiyonunu içeren bir döşeme ailesi üretir. Penrose döşemeleri.

tetrakis kare döşeme dört paralel aileye sahip bir multigrid'i andıran, ancak ailelerden ikisinin diğer ikisinden daha geniş aralıklı olduğu ve düzenlemenin basitten çok basit olduğu periyodik bir döşeme oluşturan sonsuz bir çizgi düzenlemesidir. İkili, kesik kare döşeme. Benzer şekilde, üçgen döşeme üç paralel aileden oluşan sonsuz basit bir çizgi düzenlemesidir ve ikili olarak altıgen döşeme, ve ikiye bölünmüş altıgen döşeme altı paralel aile ve iki satır aralığı ile sonsuz basit bir çizgi düzenlemesidir. büyük eşkenar dörtgen döşeme.

Algoritmalar

İnşaat düzenlemedeki satırların bir listesi girdi olarak verilen, bu nesneler arasındaki bitişiklerle birlikte düzenlemenin köşelerinin, kenarlarının ve hücrelerinin bir temsilini hesaplayan bir düzenleme aracı, örneğin bir çift ​​bağlantılı kenar listesi. Bölge teoremi nedeniyle, düzenlemeler, önceden eklenen hatların düzenlemesine her seferinde bir satır ekleyen artımlı bir algoritma ile verimli bir şekilde oluşturulabilir: her yeni satır, zaman dilimine orantılı olarak eklenebilir ve bu da toplam inşaat süresi ile sonuçlanır. O (n2).[5] Bununla birlikte, bu algoritmanın bellek gereksinimleri yüksektir, bu nedenle, bir düzenlemenin tüm özelliklerini bir kerede tüm düzenlemeyi bellekte tutmayan bir algoritma ile rapor etmek daha uygun olabilir. Bu yine verimli bir şekilde O zamanında yapılabilir (n2) ve boşluk O (n), bir algoritmik teknik olarak bilinir topolojik tarama.[23] Bir çizgi düzenlemesini tam olarak hesaplamak, girdi koordinatlarından birkaç kat daha büyük bir sayısal kesinlik gerektirir: eğer bir çizgi üzerinde iki nokta ile belirtilmişse, düzenleme köşelerinin koordinatları bu girdi noktalarından dört kat daha fazla kesinliğe ihtiyaç duyabilir. Bu nedenle, hesaplamalı geometriler, düzenlemeleri sınırlı sayısal hassasiyetle verimli bir şekilde inşa etmek için algoritmaları da incelemiştir.[24]

Ayrıca araştırmacılar, bölgeler gibi bir düzenlemenin daha küçük bölümlerini oluşturmak için verimli algoritmalar üzerinde çalıştılar.[25] kseviyeleri,[26] veya belirli bir nokta kümesini içeren hücre kümesidir.[27] Medyan ile düzenleme tepe noktasını bulma sorunu xkoordinat (ikili bir biçimde) sağlam istatistikler hesaplama sorunu olarak Theil – Sen tahmincisi bir dizi nokta.[28]

Marc van Kreveld, hesaplamanın algoritmik problemini önerdi en kısa yollar Yolların düzenlemenin kenarlarını takip etmekle sınırlandırıldığı bir çizgi düzenlemesindeki köşeler arasında, tüm düzenleme grafiğine en kısa yol algoritmasının uygulanması için gereken ikinci dereceden zamandan daha hızlı.[29] Bir yaklaşım algoritması bilinen,[30] ve sorun, az sayıda paralel aileye giren hatlar için verimli bir şekilde çözülebilir (kentsel sokak ızgaralarında olduğu gibi),[31] ancak genel sorun açık kalıyor.

Öklid dışı hat düzenlemeleri

Dokuz psödolinden oluşan gerilemeyen bir psödolin düzenlemesi. (Dokuzdan az pseudolinin tüm düzenlemeleri gerilebilir.) Pappus'un altıgen teoremi, bu düzenleme bir projektif düzlem herhangi bir alan üzerinde.
Tarafından kullanılan bir akor diyagramına kombinasyonel olarak eşdeğer bir hiperbolik çizgi düzenlemesi Ageev (1996) bunu göstermek için üçgen içermez daire grafikler bazen ihtiyaç duyabilir 5 renk.

Bir psödolin düzenlemesi bir aile eğriler benzer paylaşan topolojik çizgi düzenlemeli özellikler.[32] Bunlar en basit şekilde şurada tanımlanabilir: projektif düzlem gibi basit kapalı eğriler herhangi ikisi tek bir geçiş noktasında buluşur.[33] Bir psödolin düzenlemesinin gerilebilir kombinatoryal olarak bir çizgi düzenlemesine eşdeğer ise; bu tamamlayınız için gerçeklerin varoluş teorisi gerilebilir düzenlemeleri gerilemeyenlerden ayırt etmek için.[34] Sonlu sayıdaki sözdizinin her düzenlemesi, Öklid dışı bir tür "yayılmış" çizgiler haline gelecek şekilde genişletilebilir. olay geometrisi bir topolojik düzlemin her iki noktasının benzersiz bir çizgiyle (Öklid düzleminde olduğu gibi) birbirine bağlandığı, ancak Öklid geometrisinin diğer aksiyomlarının uygulanamayabileceği.

Öklid dışı bir geometri türü de hiperbolik düzlem, vehiperbolik hatların düzenlemeleri bu geometride de çalışılmıştır. Öklid düzlemindeki herhangi bir sonlu çizgi kümesi, hiperbolik düzlemde kombinatoryal olarak eşdeğer bir düzenlemeye sahiptir (örneğin, düzenlemenin köşelerini büyük bir daire ile çevreleyerek ve dairenin içini bir Klein modeli hiperbolik düzlemin). Ancak hiperbolik hat düzenlemelerinde çizgiler paralel olmadan birbirlerini kesmekten kaçınabilirler; kavşak grafiği hiperbolik bir düzenlemedeki çizgilerin daire grafiği. Pseudolinler için hiperbolik hat düzenlemelerine karşılık gelen kavram, bir zayıf psödolin düzenlemesi,[35] çizgilerle aynı topolojik özelliklere sahip bir eğri ailesi[36] öyle ki ailedeki herhangi iki eğri ya tek bir kesişme noktasında buluşur ya da kesişmez.

Ayrıca bakınız

  • Yapılandırma (geometri), tüm çizgilerin aynı sayıda nokta içeren ve tüm noktaların aynı sayıda çizgiye ait olduğu bir çizgi düzeni ve bir dizi nokta.
  • Düzenleme (boşluk bölümü), eğrilerin veya yüzeylerin düz olmasını gerektirmeden, üst üste binen eğriler tarafından verilen düzlemin veya üst üste binmiş yüzeyler tarafından daha yüksek boyutlu bir boşluğun bir bölümü.
  • K seti (geometri) k-kümeleri, hat düzenlemelerinde projektif dualite ile k-seviyeleriyle ilişkilidir.
  • Matematiksel Köprü İngiltere, Cambridge'de, kirişlerinin kemerine teğet çizgilerden oluşan bir düzenleme oluşturan bir köprü

Notlar

  1. ^ Bir düzenlemenin yerel olarak sonlu olması için, düzlemin her sınırlı alt kümesi yalnızca sonlu sayıda çizgi ile geçilebilir.
  2. ^ Grünbaum (1972), sayfa 4.
  3. ^ Steiner (1826); Agarwal ve Sharir (2000).
  4. ^ Yatay bir alt kenarın bulunduğu hücreler için, en alttaki tepe noktasını, alt kenarın sağ uç noktası olacak şekilde seçin.
  5. ^ a b Chazelle, Guibas ve Lee (1985), Edelsbrunner (1987), Edelsbrunner, O'Rourke ve Seidel (1986).
  6. ^ a b Bern vd. (1991).
  7. ^ Aronov, Matoušek ve Sharir (1994).
  8. ^ Dey (1998); Tóth (2001). Karmaşıklığı sınırlama sorunu k-seviyeler ilk olarak tarafından çalışıldı Lovász (1971) ve Erdős vd. (1973).
  9. ^ Alon ve Győri (1986).
  10. ^ Balogh vd. (2004); Ayrıca bakınız Matoušek (1991).
  11. ^ Canham (1969); Clarkson vd. (1990).
  12. ^ Ajtai vd. (1982); Leighton (1983).
  13. ^ Székely (1997).
  14. ^ Melchior (1940); Grünbaum (2009).
  15. ^ Grünbaum (1972); Grünbaum (2009).
  16. ^ Grünbaum (2009)
  17. ^ Crowe ve McKee (1968); Dirac (1951); Kelly ve Moser (1958); Grünbaum (1972), sayfa 18.
  18. ^ Eppstein, Falmagne ve Ovchinnikov (2007).
  19. ^ Eppstein (2006).
  20. ^ Grünbaum (1972); Levi (1926); Roudneff (1988).
  21. ^ Füredi ve Palásti (1984); Grünbaum (1972).
  22. ^ Purdy (1979); Purdy (1980); Strommer (1977).
  23. ^ Edelsbrunner ve Guibas (1989).
  24. ^ Fortune ve Milenkovic (1991); Greene ve Yao (1986); Milenkoviç (1989).
  25. ^ Aharoni vd. (1999).
  26. ^ Agarwal vd. (1998); Chan (1999); Cole, Sharir ve Yap (1987); Edelsbrunner ve Welzl (1986).
  27. ^ Agarwal (1990); Agarwal, Matoušek ve Sharir (1998); Edelsbrunner, Guibas ve Sharir (1990).
  28. ^ Cole vd. (1989).
  29. ^ Erickson (1997).
  30. ^ Bose vd. (1996).
  31. ^ Eppstein ve Hart (1999).
  32. ^ Grünbaum (1972); Agarwal ve Sharir (2002).
  33. ^ Bu tanım Grünbaum (1972). Alternatif psödolin tanımlarının karşılaştırması için bkz. Eppstein, Falmagne ve Ovchinnikov (2007).
  34. ^ Shor (1991); Schaefer (2010).
  35. ^ de Fraysseix ve Ossona de Mendez (2003).
  36. ^ İşte alternatif bir tanım Shor (1991), sözdeolin, bir alt çizginin görüntüsüdür. homomorfizm uçağın uygun.

Referanslar

Dış bağlantılar