Steinerův bod (výpočetní geometrie) - Steiner point (computational geometry)

Příklad Steinerových bodů (červeně) přidaných do triangulace ke zlepšení kvality trojúhelníků.

v výpočetní geometrie, a Steinerův bod je bod, který není součástí vstupu do úlohy geometrické optimalizace, ale je přidán během řešení úlohy, aby se vytvořilo lepší řešení, než by bylo možné pouze z původních bodů.

Název těchto bodů pochází z Problém Steinerova stromu, pojmenoval podle Jakob Steiner, ve kterém je cílem spojit vstupní body sítí o minimální celkové délce. Pokud jsou samotné vstupní body použity jako koncové body okrajů sítě, pak je nejkratší síť jejich minimální kostra. Kratší sítě však lze často získat přidáním Steinerových bodů a použitím nových bodů i vstupních bodů jako koncových bodů hrany.[1]

Dalším problémem, který využívá Steinerovy body, je Steinerova triangulace. Cílem je rozdělit vstup (například množinu bodů nebo mnohoúhelník) na trojúhelníky, které se setkávají od okraje k okraji. Vstupní body i Steinerovy body lze použít jako vrcholy trojúhelníků.[2]

Reference

  1. ^ Hwang, F. K .; Richards, D. S .; Winter, P. (1992), Problém Steinerova stromu, Annals of Discrete Mathematics, 53, Elsevier, ISBN  0-444-89098-X.
  2. ^ de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), Výpočetní geometrie: Algoritmy a aplikace (2. vyd.), Springer, str. 293, ISBN  9783540656203