Stervormige veelhoek: verschil tussen versies

2 bytes toegevoegd ,  7 jaar geleden
geen bewerkingssamenvatting
 
==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 half-vlakken. 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> 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</ref> presenteerden een algoritme om de doorsnede van de inwendige half-vlakken in optimale [[Big Grote-O -notatie|Θ]](''N'') tijd te construeren.
 
==Zie ook==
42.429

bewerkingen