Stervormige veelhoek: verschil tussen versies

20 bytes verwijderd ,  2 jaar geleden
 
== 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 [[Grote-O-notatie|Θ]](''N'') tijd te construeren.