Stervormige veelhoek

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een stervormige veelhoek (boven). De kern wordt beneden in het rood getoond.

Een stervormige veelhoek (niet te verwarren met een sterveelhoek) is een veelhoekige regio in het vlak, die een stervormige verzameling is, dat wil zeggen dat een veelhoek P stervormig is, wanneer er een punt z bestaat, zodanig dat voor elk punt p van P het lijnstuk zp in zijn geheel binnen veelhoek P ligt.[1]

De verzameling van alle punten z met de beschreven eigenschap wordt de kern van P genoemd.

Gebruik[bewerken]

Stervormige veelhoeken zijn van belang in de algoritmische meetkunde en toepassingen daarvan, zoals bewegingsplanning, dit vanwege de relatie tussen stervormige veelhoeken en de notie van zichtbaarheid: een stervormige veelhoek kan informeel worden gedefinieerd als de veelhoek, waarvan het gehele inwendige vanuit een enkel punt zichtbaar is, als we er ten minste van uitgaan dat de grens van de veelhoek niet transparent is.

Eigenschappen[bewerken]

Convexe veelhoeken zijn stervormige verzamelingen en een convexe veelhoek valt samen met zijn eigen kern.

Inpuntige veelhoek vragen kunnen in logaritmische tijd en na voorbewerking in lineaire tijd worden beantwoord.

Kern[bewerken]

Elke ribbe van een veelhoek definieert een inwendig halfvlak, informeel gedefinieerd als een halfvlak, dat inwendige punten van het veelvlak in de nabijheid van de ribbe in kwestie bevat. De kern van een veelvlak is de doorsnede van al haar inwendige half-vlakken. De doorsnede van N willekeurige halfvlakken kan gebruikmakend van het verdeel en heers algoritme in Θ(N log N) tijd worden gevonden[1]. Lee and Preparata[2] presenteerden een algoritme om de doorsnede van de inwendige half-vlakken in optimale Θ(N) tijd te construeren.

Zie ook[bewerken]

Referenties[bewerken]

  1. a b Franco P. Preparata en Michael Ian Shamos, Computational Geometry - An Introduction (Algoritmische meetkunde - een introductie, Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; vertaald uit het Russisch, 1989: ISBN 5-03-001041-6, 1985
  2. Lee, D. T., Preparata, F.P. (1979) "An Optimal Algorithm for Finding the Kernel of a Polygon" (Een optimaal algoritme voor het vinden van de kern van een veelhoek), Journal of the ACM, Volume 26 , Issue 3 Pages: 415 - 421