Stervormige veelhoek: verschil tussen versies

603 bytes verwijderd ,  2 jaar geleden
geen bewerkingssamenvatting
(nl.wikipedia.org/wiki/Halfvlak)
[[Bestand:Star-kernel.svg|thumb|Een stervormige veelhoek (boven).met De{{legenda|#B22222|de kern wordt beneden in het rood getoond.}}]]
Een '''stervormige veelhoek''' (niet te verwarren met een [[sterveelhoek]]) is een [[veelhoek|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 (meetkunde)|punt]] ''z'' bestaat, zodanig dat voor elk punt ''p'' van ''P'' het [[lijnstuk]] ''zp'' in zijn geheel binnen veelhoek ''P'' ligt.<ref name=PS>{{cite book
| author = Franco P. Preparata en Michael Ian Shamos | title = Computational Geometry - An Introduction (Algoritmische meetkunde - een introductie | publisher = [[Springer Science+Business Media|Springer-Verlag]]| year = 1985 | id = 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}}</ref>
 
Een '''stervormige veelhoek''', (niet te verwarren met een [[sterveelhoek]]), is een [[veelhoek|veelhoekige regio]] in het [[Vlak (meetkunde)|vlak]], die een [[stervormige verzameling]] is, dat wil zeggen dat een veelhoek ''P'' stervormig is, wanneer er een [[puntPunt (meetkundewiskunde)|punt]] ''z'' bestaat, zodanig dat voor elk punt ''p'' van ''P'' het [[lijnstuk]] ''zp'' in zijn geheel binnen [[veelhoek]] ''P'' ligt.<ref name=PS>{{citeen}} bookFP 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]]en ''z'' met de beschreven eigenschap is de kern van ''P''.
De [[verzameling (wiskunde)|verzameling]] van alle [[punt (meetkunde)|punt]]en ''z'' met de beschreven eigenschap wordt de '''kern''' van ''P'' genoemd.
 
In een convexe veelhoek valt de kern van de veelhoek samen met de gehele veelhoek.
 
== Gebruik ==
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 (meetkunde)|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 transparant is.
 
== Eigenschappen ==
[[Convexe veelhoek]]en zijn [[stervormige verzameling]]en 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 ==
Elke [[ribbe]] van een veelhoek definieert een '''inwendig [[halfvlak (meetkunde)|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, D.en T.,FP Preparata, F.P.voor (1979) "[[Association for Computing Machinery|Journal of the ACM]]. An Optimal Algorithm for Finding the Kernel of a Polygon" (Een optimaal algoritme voor het vinden van de kern van een veelhoek), Journal1979. of the ACM, Volumev 26 , Issuei 3, Pages:pp. 415 - 421</ref> presenteerden een algoritme om de doorsnede van de inwendige halfvlakken in optimale [[Grote-O-notatie|Θ]](''N'') tijd te construeren.
 
== Zie ook ==
* [[Zichtbaarheidsveelhoek]]
* [[Monotone veelhoek]]
 
----
== Referenties ==
{{References|85%}}