Přímočarý minimální kostra - Rectilinear minimum spanning tree

Příklad přímého minimálního kostry z náhodných bodů.

v teorie grafů, přímočarý minimální kostra (RMST) sady n body v letadlo (nebo obecněji v ℝd) je minimální kostra této sady, kde váha hrany mezi každou dvojicí bodů je přímá vzdálenost mezi těmito dvěma body.

Vlastnosti a algoritmy

Výslovným vytvořením kompletní graf na n vrcholy, které má n(n-1) / 2 hrany, přímočarý minimální kostru lze najít pomocí existujících algoritmů pro nalezení minimálního kostry. Zejména pomocí Primův algoritmus s matice sousedství poskytuje časovou složitost O (n2).

Rovinný případ

V rovinném případě existují efektivnější algoritmy. Jsou založeny na myšlence, že ke spojení může dojít pouze s nejbližším sousedem bodu v každé oktantě - tedy s každou z osmi oblastí roviny ohraničené souřadnou osou z tohoto bodu a jejich půlících čar.

Výsledný graf má pouze lineární počet hran a může být sestaven v O (n log n) používat algoritmus rozděl a panuj[1] nebo a algoritmus zatáčkové čáry.[2]

Aplikace

Elektronický design

Problém obvykle nastává v fyzický design z elektronické obvody. V moderní vysoké hustotě integrované obvody drát směrování se provádí dráty, které se skládají ze segmentů probíhajících vodorovně v jedné vrstvě kovu a svisle v jiné kovové vrstvě. Ve výsledku se délka drátu mezi dvěma body přirozeně měří s přímočarou vzdáleností. I když směrování celé sítě s více uzly lépe reprezentuje přímočarý Steinerův strom, RMST poskytuje přiměřenou aproximaci a odhad délky drátu.[3]

Viz také

Reference

  1. ^ L. J. Guibas a J. Stolfi, „O výpočtu všech severovýchodních nejbližších sousedů v metrice L1“, Information Processing Letters, 17 (1983), str. 219--223
  2. ^ Hai Zhou, Narendra Shenoy, William Nicholls, „Efektivní minimální konstrukce překlenujícího stromu bez Delaunayovy triangulace“, Information Processing Letters 81 (2002) 271–276
  3. ^ F. K. Hwang. „Na Steinerovi minimum stromů s přímočarou vzdáleností.“ SIAM Journal on Applied Mathematics, 30:104–114, 1976.