Egyenes élű síkgráf
Az egyenes élű síkgráf (Planar straight-line graph, PSLG) a számítási geometria területén használatos fogalom egy síkbarajzolható gráf olyan síkba ágyazására, amiben az éleket egyenes szakaszok testesítik meg.[1] A Fáry-tétel (1948) állítása szerint minden síkgráfhoz tartozik ilyen síkba ágyazás.
A számítási geometria területén a PSLG-ket gyakran planar subdivision-nek (kb. síkfelosztások) nevezik, annak feltételezésével, hogy ezek a felosztások sokszög alakúak.
Az olyan egyenes élű síkgráfok, melyeknek nincsenek 1 fokszámú csúcsaik a síkot sokszög alakú régiókra osztják, és fordítva. Az 1 fokszám nélküli csúcsok hiánya számos algoritmust leegyszerűsít, de általában nem lényeges feltétel.
A PSLG-k különböző térképek, akár földrajzi információs rendszerek térképeinek reprezentációjára is szolgálhatnak.
A PSLG-k speciális esetei a háromszögelések (sokszög háromszögekre bontása, ponthalmaz háromszögelése). A ponthalmazok háromszögelései maximális egyenes élű síkgráfok abban az értelemben, hogy nem lehetséges egyenes élekkel kiegészíteni őket. A háromszögeléseknek különböző területeken számos felhasználásuk létezik.
Az egyenes élű síkgráfok felfoghatók speciális euklideszi gráfokként is. Az euklideszi gráfok tárgyalásakor azonban főként a metrikus tulajdonságokkal, pl. a csúcsok közötti távolságokkal szokás foglalkozni, míg az egyenes élű síkgráfoknál főleg a topologikus tulajdonságokkal. Egyes gráfoknál, például a Delaunay-háromszögelések esetében a metrikus és topologikus tulajdonságok is fontosak lehetnek.
PSLG-vel kapcsolatos problémák szerkesztés
- Pont helyzete. Adott pont esetében kíváncsiak vagyunk, a PSLG melyik tartományához tartozik.
- Térképek átfedése. Keressük meg két PSLG (térkép) átfedését, ami a sík felosztása két egyszerre beágyazott PSLG-vel. A térinformatikában ezt a problémát „tematikus térképek átfedésének” nevezik.
Kapcsolódó szócikkek szerkesztés
- Kétszeresen összekötött élek listája (Doubly connected edge list, DCEL), a PSLG-k tárolására használt adatstruktúra
- Local feature size
Jegyzetek szerkesztés
- ↑ Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6 (1985)