Momenttikäyrä

Momenttikäyrä on algebrallinen käyrä d - ulotteisessa euklidisessa avaruudessa , jonka antaa joukko pisteitä, joilla on suorakulmaiset koordinaatit .

[1] [2] .

Euklidisessa tasossa momenttikäyrä on paraabeli , ja kolmiulotteisessa avaruudessa se on kierretty kuutiokäyrä . Sen sulkeutuminen projektiiviseen avaruuteen on rationaalinen normaalikäyrä .

Momenttikäyriä käytetään joissakin kombinatorisen geometrian sovelluksissa , kuten syklisissä polyhedraissa , "ei kolmea pistettä samalla viivalla" -ongelmassa geometrisessa todisteessa Kneser-kaavioiden kromaattisesta lukumäärästä .

Ominaisuudet

Jokaisella hypertasolla on enintään d yhteistä pistettä käyrän kanssa. Jos hypertasolla on täsmälleen d yhteistä pistettä käyrän kanssa, käyrä leikkaa hypertason kussakin sellaisessa pisteessä (eli ei kosketa). Siten mikä tahansa äärellinen pistejoukko momenttikäyrällä on yleisessä lineaarisessa asemassa [3] [4] [5] .

Sovellukset

Minkä tahansa momenttikäyrän äärellisen pistejoukon kupera runko on syklinen monitahoinen [6] [7] [4] . Syklisillä monitahoilla on eniten kasvoja tietylle määrälle pisteitä, ja ulottuvuuksissa neljä ja sitä suuremmissa monitahoilla on ominaisuus, että niiden reunat muodostavat täydellisen graafin . Tarkemmin sanottuna ne ovat vierekkäisyyspolytooppeja , mikä tarkoittaa, että mikä tahansa polytoopin korkeintaan d /2 kärkien joukko muodostaa sen yhden pinnan. Momenttikäyrän pistejoukko sisältää myös suurimman mahdollisen määrän yksinkertaistuksia, kaikkien mahdollisten Delaunay -kolmioiden joukossa n pisteen joukosta d - ulotteisessa avaruudessa [8] .

Euklidisessa tasossa mikä tahansa mitattavissa oleva alue voidaan jakaa neljään yhtä suureen osajoukkoon ( sandwich-lauseen avulla ). Samalla tavalla, mutta monimutkaisemmin, mikä tahansa mitattavissa oleva joukko kolmiulotteisessa avaruudessa voidaan jakaa kahdeksaan yhtä suureen (mittaamalla) osajoukkoon kolmella tasolla. Tämä tulos ei kuitenkaan yleisty viiteen tai useampaan ulottuvuuteen, koska momenttikäyrä antaa esimerkin joukoista, joita ei voida hajottaa 2 d :n osajoukkoon d hypertasolla. Erityisesti viisiulotteisessa avaruudessa viiden hypertason joukko voi jakaa momenttikäyrän enintään 26 segmenttiin. Ei tiedetä, onko 4D-momenttikäyrä aina mahdollista jakaa 16 yhtä suureen osaan viidellä hypertasolla, mutta on mahdollista jakaa 16 pistettä 4D-momenttikäyrästä neljän hypertason joukon 16 ortanttiin [9] [10 ] .

Momenttikäyrään perustuvaa konstruktiota voidaan käyttää myös Galen lemman todistamiseen, jonka mukaan mille tahansa positiiviselle k :lle ja d :lle voidaan sijoittaa 2 k  +  d pistettä d - ulotteiselle pallolle siten, että mikä tahansa avoin puolipallo sisältää vähintään k :n. pisteitä. Tätä lemmaa voidaan puolestaan ​​käyttää Kneser-graafien kromaattisen lukumäärän laskemiseen , ongelman, jonka Laszlo Lovas ratkaisi eri tavalla [11] [12] .

Momenttikäyrää käytetään myös graafin visualisoinnissa osoittamaan, että kaikki graafit, joissa on n kärkeä, voidaan piirtää pisteillä kolmiulotteiseen kokonaislukuhilaan, jonka sivun pituus on O( n ) ilman, että kulmat ylittävät reunoja. Pääajatuksena on valita n:tä suurempi alkuluku p ja sijoittaa graafin kärjet i pisteeseen, jossa on koordinaatit

( i , i 2  mod  p , i 3  mod  p ) [13] .

Tällöin taso voi leikata käyrän vain kolmessa pisteessä. Koska kahdella leikkaavalla reunalla on oltava neljä kärkeä samassa tasossa, näin ei voi tapahtua. Samanlainen rakenne käyttää momenttien käyrää modulo alkulukua, mutta kaksiulotteisessa avaruudessa, ei kolmiulotteisessa, mikä antaa lineaarisen rajan pisteiden lukumäärälle ongelmalle "ei kolmea pistettä yhdellä suoralla" . [neljätoista]

Muistiinpanot

  1. ↑ Matousek, 2002 , s. 97, määritelmä 5.4.1.
  2. ↑ Matousek, 2003 , s. 17, Määritelmä 1.6.3.
  3. ↑ Edelsbrunner, 1987 , s. 100.
  4. ↑ 1 2 Matousek, 2002 , s. 97, Lemma 5.4.2.
  5. ↑ Matousek, 2003 , s. 17, Lemma 1.6.4.
  6. ↑ Gale, 1963 .
  7. ↑ Edelsbrunner, 1987 , s. 101.
  8. ↑ Amenta, Attali, Devillers, 2007 .
  9. ↑ Edelsbrunner, 1987 , s. 70–79.
  10. ↑ Matousek, 2003 , s. 50–51.
  11. ↑ Matousek, 2003 , s. 64–67, jakso 3.5, Galen lemma ja Schreiverin lause.
  12. ↑ Bárány, 1978 , s. 325–326, Galen lemman käyttö väritysongelmaan.
  13. ↑ Cohen, Eades, Lin, Ruskey, 1997 .
  14. ↑ Roth ( 1951 ) pitää tehtävän Erdősin ansioksi .

Kirjallisuus