Stervormige veelhoek: verschil tussen versies

102 bytes toegevoegd ,  2 jaar geleden
meer dimensies
(meer dimensies)
 
[[Bestand:Star-kernel.svg|thumb|stervormige veelhoek met {{legenda|#B22222|de kern}}]]
 
Een '''stervormige veelhoek''', niet te verwarren met een [[sterveelhoek]], is een veelhoekige regio in het [[Vlak (meetkunde)|vlak]], die een [[stervormige verzameling]] is, dat wil zeggen dat een veelhoek ''P'' stervormig is, wanneer er een [[Punt (wiskunde)|punt]] ''z'' bestaat, zodanig dat voor elk punt ''p'' van ''P'' het [[lijnstuk]] ''zp'' in zijn geheel binnen [[veelhoek]] ''P'' ligt.<ref name=PS>{{en}} FP Preparata en MI Shamos. Computational Geometry - An Introduction, 1985 ISBN 0-387-96131-3, 2e druk 1988 ISBN 3-540-96131-3, {{ru}} vertaald uit het Russisch, 1989: ISBN 5-03-001041-6</ref> De [[Verzameling (wiskunde)|verzameling]] van alle [[punt (meetkunde)|punt]]enpunten ''z'' met de beschreven eigenschap is de kern van ''P''.
 
In een convexe veelhoek valt de kern van de veelhoek samen met de gehele veelhoek.
== Kern ==
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 halfvlakken. De doorsnede van ''N'' willekeurige halfvlakken kan gebruikmakend van het verdeel en heers algoritme in [[Grote-O-notatie|Θ]](''N'' log ''N'') tijd worden gevonden.<ref name=PS/> Lee and Preparata<ref>{{en}} DT Lee en FP Preparata voor [[Association for Computing Machinery|Journal of the ACM]]. An Optimal Algorithm for Finding the Kernel of a Polygon, 1979. v 26, i 3, pp. 415 - 421</ref> presenteerden een algoritme om de doorsnede van de inwendige halfvlakken in optimale Θ(''N'') tijd te construeren.
 
== Drie dimensies ==
Een stervormig [[veelvlak]] en de daarbij behorende kern laten zich op dezelfde manier definiëren.