Egyenes vonal konfiguráció

A vonalak konfigurációja (vagy egy sík felosztása vonalakkal ) [1]  egy sík partíciója , amelyet vonalak halmaza alkot . A vonalkonfigurációkat a kombinatorikus geometriában tanulmányozzák , a számítási geometriában pedig algoritmusokat építenek a konfigurációk hatékony felépítésére.

Definíció

Az euklideszi síkon bármely A vonalhalmazra definiálhatunk egy ekvivalencia-relációt a sík pontjain, amely szerint két p és q pont ekvivalens, ha az A -ból származó bármely l egyenesre p és q egyaránt a l egyenes , vagy ugyanabban a nyitott félsíkban fekszenek, amelyet az l egyenes határol . Ha A véges vagy lokálisan véges [2] , akkor ezen relációk ekvivalenciaosztályai három csoportba tartoznak:

  1. korlátos vagy korlátlan konvex sokszögek ( dekompozíciós cellák ) belsejei, a síkban lévő pontok egy részhalmazának összekapcsolt összetevői, amelyek nem szerepelnek az A -ból származó egyeneseken sem ,
  2. nyílt szakaszok és nyitott végtelen sugarak ( dekompozíciós élek ), egyetlen egyenes olyan pontjainak összefüggő összetevői, amelyek nem tartoznak az A -ból származó másik egyeneshez ,
  3. külön pontok ( a partíció csúcsai ), két vagy több egyenes metszéspontja az A -ból .

Ez a három típusú objektum egymáshoz kapcsolva a síkot lefedő csempét alkot. A két vonalelrendezést izomorfnak vagy kombinatorikusan ekvivalensnek nevezzük, ha a cellapartíciókban lévő objektumok között egy az egyhez szomszédosságot megőrző megfeleltetés van [3]

A halmazok összetettsége

A közvetlen kezdetű konfigurációk tanulmányozása Jacob Steiner , aki az első korlátot bizonyította, hogy egy konfiguráció legfeljebb hány különböző típusú elemet tartalmazhat [4] [5] . Egy n egyenesből álló konfigurációnak legfeljebb n ( n  − 1)/2 csúcsa van, metsző csúcspáronként egy. Ez a maximum egyszerű konfigurációk esetén érhető el . Egy konfigurációt egyszerűnek nevezünk, ha

1. három egyenes nem metszi egymást egy pontban 2. nincs két párhuzamos egyenes.

Bármely konfigurációban n végtelen lefelé irányuló sugár lesz, soronként egy. Ezek a sugarak a partíció n  + 1 celláját választják el, amelyek alulról határtalanok. Az összes többi cellának egyetlen legalacsonyabb csúcsa van, [6] és minden ilyen csúcs egyetlen cella esetében az alsó, tehát a partíciós cellák száma megegyezik a csúcsok számával plusz n  + 1, vagy nem haladja meg az n értéket ( n  + 1)/2 + 1, lásd alább központi sokszögszámok . A partícióélek száma nem haladja meg az n 2 -t , ami vagy az Euler karakterisztikával , a csúcsok és cellák számát helyettesítve, vagy azzal a megfigyeléssel, hogy minden vonal legfeljebb n élre van osztva további n  − 1 sorral. Ismételten, a legrosszabb eset, amikor elérik a határt, az egyszerű vonalkonfigurációk.

Az l vonal zónája egy vonalhalmazban olyan cellák halmaza, amelyek élei l -en helyezkednek el . A zónatétel kimondja, hogy egy zóna celláiban az élek teljes száma lineáris. Pontosabban, az l vonal egyik oldalán elhelyezkedő cellaélek száma (a vonal zónájából) nem haladja meg az 5 n  − 1 értéket [7] [8] [9] , és a cellaélek teljes száma l mindkét oldalán nem haladja meg a [10] -et . Általánosabban, a konvex görbével metszett partíciós cellák teljes komplexitása O( n  α( n )), ahol α az inverz Ackermann-függvényt jelöli , ami a Davenport–Schinzel szekvenciákból [10] mutatható ki. . Az összes zóna komplexitását összegezve megállapítható, hogy a partíció cellái komplexitásának négyzetének összege O( n 2 ) [11] .

A vonalak konfigurációjának k-szintje olyanvonallánc, amelyet olyan élek alkotnak, amelyek alatt pontosankmásik vonal van (azaz az élről lehúzott sugár pontosankvonalat metsz),a ≤k szint pedig az összes alkatrészvonal konfiguráció akszint alatt. A kfelső és alsó komplexitási határainak megtalálásatovábbra is jelentős nyitott probléma marad a diszkrét geometriában. A legjobb felső korlát az O(nk1/3), míg a legjobb alsó korlát az Ω(nexp(c(logk)1/2)) [12] [13] [14] . Ismeretes, hogy egy ≤k-szint maximális komplexitása Θ(nk) [15] . A k-szint egy síkpartíció monoton útvonalának speciális esete, vagyis olyan élsorozat, amely egyetlen pontban metszi tetszőleges függőleges vonalat. A monoton utak azonban bonyolultabbak lehetnek, mint ak-szintek - ezekben a halmazokban vannak vonalak és monoton utak halmazai, ahol azon pontok száma, ahol az út irányt vált, Ω(n2 − o(1)) [16] [17] .

Bár egy partíció egyetlen celláját mind az n vonal határolja, általában nem lehetséges, hogy m különálló cellát n vonal határoljon . Ezzel szemben az m sejt teljes komplexitása majdnem egyenlő Θ( m 2/3 n 2/3  +  n ) [18] [19] és csaknem ugyanez a határ jelenik meg a Szemerédy–Trotter tételben a pontok és vonalak a síkban. Ennek a ténynek egy egyszerű bizonyítéka a metszésszám-egyenlőtlenségből következik  - ha m cellának összesen x  +  n éle van, akkor létrehozhat egy gráfot m csúcsgal (cellánként egy) és x éllel (egy soronkénti egymást követő cellapáronként egy ). sor) [20] [21] . Ennek a gráfnak az élei olyan görbékként rajzolhatók meg, amelyek nem metszik egymást az élek végpontjainak megfelelő cellákon belül, majd követik a halmaz egyeneseit. Így ezen az ábrán O( n 2 ) metszéspont található. A metszéspontszám-egyenlőtlenség alapján azonban vannak Ω( x 3 / m 2 ) metszéspontok. Ahhoz, hogy mindkét egyenlőtlenség teljesüljön, x - nek O( m 2/3 n 2/3 ) -nak kell lennie [22] .

Projektív konfigurációk és projektív kettősség

Gyakran célszerű az egyenesek konfigurációját nem az euklideszi térben, hanem a projektív síkban tanulmányozni , mivel a projektív geometriában minden egyenespárnak van metszéspontja. Projektív síkon nem definiálhatunk partíciót a vonalak oldalaival (egy projektív síkon lévő egyenes nem osztja a síkot két különálló oldalra), de a partíciócellákat továbbra is meghatározhatjuk olyan pontok összekapcsolt összetevőjeként, amelyek nem fekszenek bármilyen vonalat. Az élek összefüggő komponensek, amelyek egyetlen egyeneshez tartozó ponthalmazokból állnak, a csúcsok pedig olyan pontok, ahol két vagy több egyenes metszi egymást. A projektív síkban lévő vonalak halmaza eltér euklideszi megfelelőjétől, mivel az egyenes két oldalán lévő két euklideszi sugarat a projektív síkban egyetlen él helyettesíti, és a projektív síkban a határtalan euklideszi sejtpárok egyetlen élre cserélődnek. sejteket.

Tekintettel a projektív kettősségre , a síkban lévő pontok kombinatorikus tulajdonságaira vonatkozó számos állítás egyszerűbben értelmezhető a vonalkonfigurációkra vonatkozó ekvivalens duális formában. Például Sylvester tétele , amely kimondja, hogy a síkban a pontok bármely nem kollineáris halmazának van egy egyszerű egyenese , amely pontosan két pontot tartalmaz, a projektív dualitás révén azzá az állítássá válik, hogy minden olyan konfigurációnak, amelynek több csúcsa van , egyszerű pont , az a csúcs, ahol mind a két egyenes. Sylvester tételének legkorábbi ismert bizonyítéka Melchior által ( Melchior (1940 )) az Euler-karakterisztikát használja .

Háromszögek vonalhalmazokban

A projektív síkban lévő vonalak konfigurációját egyszerűnek mondjuk, ha a partíció bármely celláját pontosan három él határolja. Az egyszerű konfigurációkat először Melchior [23] [24] tanulmányozta . Az egyszerű sorhalmazok három végtelen családja ismert:

  1. A közeli köteg n − 1 vonalból áll,  amelyek áthaladnak egy ponton, és egy olyan vonalból, amely nem halad át ezen a ponton,
  2. A szabályos sokszög oldalaiból a szimmetriatengelyekkel együtt alkotott egyenesek családja
  3. Egy páros szabályos sokszög oldalai és szimmetriatengelyei a végtelenben lévő egyenessel együtt.

Ezen kívül sok más példa is létezik egyetlen egyszerű konfigurációra , amely nem illeszthető bele egyetlen ismert végtelen családba sem [25] [24] . Ahogy Grünbaum [24] írja , az egyszerű vonalhalmazok "példaként vagy ellenpéldaként jelennek meg a kombinatorikus geometria és alkalmazásai számos kontextusában". Például Artier, Grünbaum és Llibre [26] egyszerű sorhalmazokat használt, hogy ellenpéldákat hozzon létre a differenciálegyenlet -halmaz hatványai és az egyenletben előforduló invariáns egyenesek száma közötti kapcsolatra vonatkozó sejtésre. A Dirac-Motzkin sejtés két jól ismert ellenpéldája (amely azt állítja, hogy bármely n sorból álló konfigurációnak legalább n /2 egyszerű pontja van) mindkettő egyszerű [27] [28] [29] [30] .

Egy olyan vonalkonfiguráció kettős gráfja , amelyben cellánként egy csúcs van, és egy él, amely összeköti a konfigurációban közös élű celláknak megfelelő csúcsokat, egy parciális kocka , egy gráf, amelyben a csúcsok bitvektorokkal jelölhetők úgy, hogy a grafikonon látható távolság egyenlő a jelek közötti Hamming-távolsággal . Vonalkonfigurációk esetén minden koordináta 0 értéket vesz fel a vonal egyik oldalán, a másik oldalon pedig 1-et [31] . Az egyszerű konfigurációk kettős gráfjait arra használták, hogy 3 szabályos parciális kockákból álló végtelen családokat alkossanak, amelyek izomorfak egy egyszerű zonoéder gráfjaival [32] .

Érdekes a háromszög alakú cellák szélsőséges számának tanulmányozása egy olyan konfigurációban, amely nem feltétlenül egyszerű. Minden konfigurációnak legalább n háromszögből kell állnia. Minden olyan konfigurációnak, amely csak n háromszöget tartalmaz, egyszerűnek kell lennie [25] [33] [34] . Ismeretes, hogy egy egyszerű konfigurációban a háromszögek maximális számát felülről az n ( n  − 1)/3 szám határolja, a minimális korlát pedig n ( n  − 3)/3. Az alsó korlátot egy szabályos 2 n -szög átlóinak néhány részhalmazán érjük el [35] [25] . Nem egyszerű konfigurációk esetén a háromszögek maximális száma hasonló, de szigorúbban korlátozott [36] [37] [38] . A szorosan kapcsolódó Cobon-háromszög probléma az euklideszi síkon lévő konfigurációban a nem átfedő véges háromszögek (nem feltétlenül lapok) maximális számát kéri. Néhány, de nem minden n értékhez n ( n − 2  )/3 háromszög lehet.

Multigrid és Penrose burkolólapok

A vonalak egyszerű konfigurációjának kettős gráfja geometriailag ábrázolható rombuszhalmazként, a konfiguráció csúcsánként egy-egy, amelynek oldalai merőlegesek a csúcsban metsző egyenesekre. Ezek a rombuszok kombinálhatók egy konvex sokszög csempézésére, ha a konfiguráció véges számú vonallal rendelkezik, vagy a teljes síkot lokálisan véges konfigurációk esetén, végtelen számú vonallal. De Bruijn [39] ennek a konstrukciónak olyan speciális eseteit tanulmányozta, amelyekben a vonalak konfigurációja k párhuzamos egyenes halmazból áll, amelyek egymástól egyenlő távolságra vannak. Két egymásra merőleges párhuzamos vonalcsalád esetén ez a konstrukció egyszerűen az ismerős négyzet alakú parkettát adja a síkban, három, egymással 120 fokos szögben elhelyezkedő vonalcsaládnál (így egy háromhatszögletű burkolóanyagot képezve ) a konstrukció rombuszos burkolást ad . Ez a konstrukció azonban nagyobb számú vonalcsalád esetén időszakos burkolást ad . Pontosabban, öt egymáshoz képest egyenlő szöget bezáró vonalcsalád esetében (vagy ahogy De Bruijn ezt a konfigurációt pentagridnek nevezi ) ez egy olyan burkolólapcsaládot ad, amely a Penrose burkolólapok rombusz alakú változatát tartalmazza .

Az osztott négyzetes  csempézés vonalak végtelen konfigurációja, amely periodikus tesszelációt alkot, amely négy párhuzamos családdal rendelkező több rácsra hasonlít, de amelyben két család vonalai közötti távolság nagyobb, mint a másik kettő, és amelyben a vonalak halmaza egyszerű. nem pedig egyszerű. A kettős csempézés a csonka négyzet burkolat . Hasonlóképpen, a háromszög alakú csempézés egy végtelen egyszerű konfiguráció vonalak három családjával párhuzamos vonalak, amelyek kettős csempézése egy hatszögletű mozaik , és egy osztott hatszögletű csempészet egy végtelen egyszerű konfiguráció vonalak hat családjával párhuzamos vonalakkal és kettővel. vonalak közötti távolság a családokban, ami kettős a nagy rombusz-háromhatszögletű csempével .

Algoritmusok

A konfiguráció létrehozása egy vonalkonfiguráció csúcsainak, éleinek és celláinak reprezentációjának kiszámítását jelenti (a kapcsolataikkal együtt), ha egy halmazban vonallistát kapunk, például egy duplán összekapcsolt éllistát . A zónatétel szerint a halmazok hatékonyan építhetők fel egy növekményes algoritmussal, amely lépésenként egy sort ad az előző lépésekben hozzáadott sorok halmazához – minden új sor a zónájával arányos időben adható hozzá, ami O( n ) időt eredményez. 2 ) [7] . Ennek az algoritmusnak a memóriaigénye azonban magas, ezért kényelmesebb lehet az összes konfigurációs tulajdonságot felsorolni egy olyan algoritmusban, amely nem tárolja az összes konfigurációt a memóriában. Ez hatékonyan megtehető O( n 2 ) időben és O( n ) térben a topológiai balayage néven ismert algoritmikus technikával [40] . A vonalkonfiguráció pontos kiszámítása a bemeneti adatoknál (koordinátáknál) többszörös számítási pontosságot igényel - ha az egyenest két pont adja meg rajta, akkor a csúcskonfiguráció koordinátái a bemeneti adatpontok pontosságának négyszeresét is megkívánhatják. Ezért a konfigurációk hatékony, korlátozott numerikus pontosságú felépítésére szolgáló algoritmusokat a számítási geometriában is tanulmányozzák [41] [42] [43] .

A kutatók hatékony algoritmusokat is tanulmányoztak egy konfiguráció kisebb részei, például zónák [44] , k - szintek [45] [46] [47] [48] vagy adott pontkészletet tartalmazó cellák [49] létrehozására. [50] [51] . A medián x koordinátákkal rendelkező csúcsok konfigurációjának megtalálásának problémája a robusztus statisztikában (duális formában) egy ponthalmaz Theil-Sen becslésének kiszámításának problémájaként merül fel [52] .

Mark van Creveld egy algoritmikus problémát javasolt a csúcsok közötti legrövidebb út kiszámítására olyan vonalkonfigurációban , ahol az útvonalakat a konfiguráció élei határolják. A probléma a következő: vannak-e olyan algoritmusok, amelyek egy négyzetes időnél rövidebb idő alatt működnek, amelyet az algoritmus a legrövidebb út megtalálására fordítana egy teljes konfigurációs gráfban [53] . Ismeretes egy közelítő algoritmus [54] , és a probléma hatékonyan megoldható olyan vonalakra, amelyek kis számú párhuzamos vonalcsaládra oszlanak (ami jellemző a városi utcákra) [55] , de a probléma általában nyitott marad.

Változatok és általánosítások

Pseudoline konfiguráció

A pszeudolinok  konfigurációja olyan görbék konfigurációja , amelyek hasonló topológiai tulajdonságokkal rendelkeznek, mint a vonalak konfigurációja [25] [56] . Legegyszerűbben a projektív síkon egyszerű zárt görbékként definiálhatók, amelyek közül bármelyik kettő keresztirányban egy pontban metszi egymást. A pszeudolinok konfigurációját akkor mondjuk bővíthetőnek , ha kombinatorikusan ekvivalens vonalak konfigurációjával. Az egyenirányítható és nem egyenirányítható halmazok megkülönböztetésének problémája [57] [58] NP- teljes . Véges számú pszeudolin bármely konfigurációja kiterjeszthető úgy, hogy a pszeudolinok vonalakká váljanak egy nem euklideszi beesési geometriában , amelyben a topológiai sík bármely két pontja egyetlen egyenessel van összekötve (mint az euklideszi síkban), de amelyet az euklideszi geometria többi axiómája esetleg nem tart meg.


Kilenc pszeudovonal kiterjeszthetetlen halmaza. (Minden kilencnél kevesebb pszeudolint tartalmazó gyűjtemény rektifikálható.) Pappus tétele szerint ez a konfiguráció egyetlen mező feletti projektív síkban sem valósítható meg .
A vonalak hiperbolikus konfigurációja kombinatorikusan ekvivalens a húrdiagrammal, amelyet Ageev [59] használt annak bizonyítására, hogy egy háromszög nélküli körgráf néha öt színt igényel .

Lobacsevszkij repülőgép

A nem euklideszi geometria egy másik típusa a Lobacsevszkij-sík , és ebben a geometriában a hiperbolikus vonalak konfigurációit is tanulmányozták. Az euklideszi sík bármely véges egyeneshalmaza kombinatorikusan ekvivalens konfigurációval rendelkezik a hiperbolikus síkban (például a halmaz csúcsait egy nagykörbe zárja, és a ciklus belsejét a hiperbolikus sík Klein-modelljeként értelmezi ). Hiperbolikus egyeneshalmazban azonban elkerülhető az egyenesek metszéspontja anélkül, hogy az egyenesek párhuzamosak legyenek. A hiperbolikus konfigurációban a metszéspont gráf egy kördiagram . A pszeudolinok vonalainak hiperbolikus konfigurációjának megfelelő fogalma a pszeudolinok gyenge konfigurációja [60] , olyan görbecsalád, amely ugyanazokkal a topológiai tulajdonságokkal rendelkezik, mint a vonalak [61] , így a család bármely két görbéje vagy metszi egymást egy pontban, vagy egyáltalán nem metszik egymást.

Lásd még

Jegyzetek

  1. ↑ Az angol szakirodalomban az elrendezés , amelyet gyakran konfigurációnak fordítanak , van azonban egy másik konfigurációs kifejezés is, amelyet természetesen a konfiguráció szónak is fordítanak . Néha a vonalkészlet kifejezést használják , néha - partíció (vonalakkal vagy hipersíkokkal).
  2. ↑ Lokálisan véges halmazokban a sík bármely korlátos részhalmazát csak véges számú egyenes metszi.
  3. ↑ Grünbaum, 1972 , p. négy.
  4. ↑ Steiner, 1826 .
  5. ↑ Agarwal, Sharir, 2000 .
  6. ↑ Vízszintes alsó éllel rendelkező cellák esetén válassza ki a jobb oldali csúcsot.
  7. ↑ 12 Chazelle et al, 1985 .
  8. ↑ Edelsbrunner, 1987 .
  9. ↑ Edelsbrunner, O'Rourke, Seidel, 1986 .
  10. ↑ 1 2 Bern, Eppstein, Plassman, Yao, 1991 .
  11. ↑ Aronov, Matousek, Sharir, 1994 .
  12. ↑ Dey, 1998 .
  13. ↑ Tóth, 2001 .
  14. ↑ A k -szintek komplexitásának korlátozásának problémáját először Lovász (1971 ) és Erdős, Simons, Straus csoportja vizsgálta ( Erdős et al (1973 )).
  15. ↑ Alon, Győri, 1986 .
  16. ↑ Balogh et al, 2004 .
  17. ↑ Matousek, 1991 .
  18. ↑ Canham, 1969 .
  19. ↑ Clarkson et al, 1990 .
  20. ↑ Ajtai, Chvátal, Újszülött, Szemerédi, 1982 .
  21. ↑ Leighton, 1983 .
  22. ↑ Székely, 1997 .
  23. ↑ Melchior, 1940 .
  24. ↑ 1 2 3 Grünbaum, 2005 .
  25. ↑ 1 2 3 4 Grünbaum, 1972 .
  26. ↑ Artés, Grünbaum, Llibre, 1998 .
  27. ↑ Crowe, McKee, 1968 .
  28. ↑ Dirac, 1951 .
  29. ↑ Kelly, Moser, 1958 .
  30. ↑ Grünbaum, 1972 , p. tizennyolc.
  31. ↑ Eppstein, Falmagne, Ovchinnikov, 2007 .
  32. ↑ Eppstein, 2006 .
  33. ↑ Levi, 1926 .
  34. ↑ Roudneff, 1988 .
  35. ↑ Füredi, Palásti, 1984 .
  36. ↑ Purdy, 1979 .
  37. ↑ Purdy, 1980 .
  38. ↑ Strommer, 1977 .
  39. ↑ de Bruijn, 1981 .
  40. ↑ Edelsbrunner, Guibas, 1989 .
  41. ↑ Fortune, Milenkovic, 1991 .
  42. ↑ Greene, Yao, 1986 .
  43. ↑ Milenkovic, 1989 .
  44. ↑ Aharoni et al, 1999 .
  45. ↑ Agarwal, de Berg, Matousek, Schwarzkopf, 1998 .
  46. ↑ Chan, 1999 .
  47. ↑ Cole, Sharir, Yap, 1987 .
  48. ↑ Edelsbrunner, Welzl, 1986 .
  49. ↑ Agarwal, 1990 .
  50. ↑ Agarwal, Matousek, Sharir, 1998 .
  51. ↑ Edelsbrunner, Guibas, Sharir, 1990 .
  52. ↑ Cole, Salowe, Steiger, Szemerédi, 1989 .
  53. ↑ Erickson, 1997 .
  54. ↑ Bose et al, 1996 .
  55. ↑ Eppstein, Hart, 1999 .
  56. ↑ Agarwal, Sharir, 2002 .
  57. ↑ Shor, 1991 .
  58. ↑ Schaefer, 2010 .
  59. ↑ Ageev, 1996 .
  60. ↑ de Fraysseix, Ossona de Mendez, 2003 .
  61. ↑ Shor (1991 ) alternatív definíciója – a pszeudovonal egy sík homeomorfizmus vonalának képe .

Irodalom

Linkek