For faster navigation, this Iframe is preloading the Wikiwand page for Stervormige veelhoek.

Stervormige veelhoek

Uit Wikipedia, de vrije encyclopedie

stervormige veelhoek met ■ de kern
stervormige veelhoek met
 de kern

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]

Kern

De verzameling van alle punten z met de beschreven eigenschap is de kern van P. De kern valt in een convexe veelhoek samen met de gehele veelhoek.

Iedere zijde van een veelhoek definieert een inwendig halfvlak, informeel gedefinieerd als een halfvlak, dat inwendige punten van het veelvlak in de nabijheid van de zijde 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 Θ(N log N) tijd worden gevonden.[1] Lee and Preparata[2] presenteerden een algoritme om de doorsnede van de inwendige halfvlakken in optimale Θ(N) tijd te construeren.

Een stervormig veelvlak en de daarbij behorende kern laten zich op dezelfde manier definiëren.

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: 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.



  1. a b (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
  2. (en) DT Lee en FP Preparata voor Journal of the ACM. An Optimal Algorithm for Finding the Kernel of a Polygon, 1979. v 26, i 3, pp. 415 - 421
{{bottomLinkPreText}} {{bottomLinkText}}
Stervormige veelhoek
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.