K-set (geometrie) - K-set (geometry)

Sada šesti bodů (červená), jejích šest 2 sad (sady bodů obsažené v modrých oválech) a čáry oddělující každou sadu K od zbývajících bodů (přerušovaná černá).

v diskrétní geometrie, a k- množina konečných bodů S v Euklidovské letadlo je podmnožina z k prvky S které lze striktně oddělit od zbývajících bodů pomocí a čára. Obecněji v Euklidovský prostor vyšších rozměrů, a k-set množiny konečných bodů je podmnožina k prvky, které lze oddělit od zbývajících bodů a nadrovina. Zejména když k = n/ 2 (kde n je velikost S), čára nebo nadrovina, která odděluje a k-set od zbytku S je poloviční čára nebo poloviční letadlo.

K.-sety jsou příbuzné od projektivní dualita na k-úrovně v uspořádání linky; the k-úroveň v uspořádání n přímky v rovině je křivka skládající se z bodů, které leží na jedné z čar a mají přesně k řádky pod nimi. Diskrétní a výpočetní geometři také studovali úrovně v uspořádání obecnějších druhů křivek a ploch.^[1]

Kombinatorické hranice

Nevyřešený problém v matematice: Jaký je největší možný počet půlících čar pro sadu ${displaystyle n}$ body v letadle? (více nevyřešených úloh z matematiky)

Při analýze geometrických algoritmů je důležité omezit počet k-sady rovinné množiny bodů,^[2] nebo ekvivalentně počet k-úrovně uspořádání rovinných čar, problém nejprve studoval Lovász (1971) a Erdős et al. (1973). Nejznámější horní hranice tohoto problému je Ó(nk^1/3), jak ukázal Tamal Dey (1998) pomocí nerovnost křížení čísel Ajtai, Chvátal, Novorozenec a Szemerédi. Nejznámější dolní mez je však daleko od horní meze Dey: je to Ω (n exp (C (logk)^1/2)) pro nějakou konstantu C, jak ukazuje Toth (2001).

Ve třech rozměrech je nejlepší známá horní hranice Ó(nk^3/2) a nejlepší známá dolní mez je Ω (nk exp (C (logk)^1/2)).^[3]Pro body ve třech rozměrech, které jsou v konvexní pozice, to znamená, že jsou vrcholy některých konvexních mnohostěnů, počet k-množin je Θ ((n-k) k), který vyplývá z argumentů použitých pro ohraničení složitosti Voronoiho diagramů k-tého řádu.^[4]

Pro případ, kdy k = n/ 2 (poloviční čáry), maximální počet kombinačně odlišných čar procházejících dvěma body S které rozdělují zbývající body, když k = 1, 2, ... je

1,3,6,9,13,18,22 ... (sekvence A076523 v OEIS ).

Meze byly také prokázány na počtu ≤k-sady, kde a ≤k-set je a j-na některé j ≤ k. Ve dvou rozměrech je maximální počet ≤k-sety jsou přesně nk,^[5] zatímco v d rozměry vázané ${displaystyle O (n ^ {lfloor d / 2floor} k ^ {lceil d / 2ceil})}$.^[6]

Konstrukční algoritmy

Edelsbrunner a Welzl (1986) nejprve studovali problém konstrukce všech k-sady sady vstupních bodů nebo duálně konstrukce k- úroveň uspořádání. The kÚroveň jejich algoritmu lze zobrazit jako zametání letadla algoritmus, který vytváří úroveň v pořadí zleva doprava. Zobrazeno z hlediska k-sady bodových sad, jejich algoritmus udržuje a dynamický konvexní trup pro body na každé straně oddělovací čáry opakovaně najde a bitangens těchto dvou trupů a přesune každý ze dvou bodů tečnosti do protilehlého trupu. Chan (1999) zkoumá následné výsledky tohoto problému a ukazuje, že jej lze vyřešit časově úměrně Deyho Ó(nk^1/3) vázané na složitost k-úroveň.

Agarwal a Matoušek popsat algoritmy pro efektivní konstrukci přibližné úrovně; to znamená křivka, která prochází mezi (k - dÚroveň) a (k + d) -level pro nějaký malý aproximační parametr d. Ukazují, že lze najít takovou aproximaci, skládající se z řady úseček, které závisí pouze na n/d a ne na n nebo k.^[7]

Zobecnění matroidů

Rovinný k-úrovňový problém lze zobecnit na jednu z parametrických optimalizací v a matroid: jeden dostane matroid, ve kterém je každý prvek vážen lineární funkcí parametru λ, a pro každou možnou hodnotu λ musí najít základ minimální hmotnosti matroidu. Pokud jeden graf váhy funguje jako čáry v rovině, k-úroveň uspořádání těchto spojnicových grafů jako funkce λ hmotnosti největšího prvku v optimálním základě v jednotný matroid a Dey ukázal, že jeho Ó(nk^1/3) vázané na složitost k- úroveň lze zobecnit tak, že spočítá počet odlišných optimálních bází libovolného matroidu n prvky a pořadí k.

Například stejné Ó(nk^1/3) horní mez drží pro počítání počtu různých minimální kostry vytvořený v grafu s n hrany a k vrcholy, když mají hrany váhy, které se lineárně mění s parametrem λ. Tento problém s parametrickým minimálním spanningovým stromem byl studován různými autory a lze jej použít k řešení dalších problémů s optimalizací bicriterion spanning tree.^[8]

Nejznámější dolní mez parametrického problému s minimálním rozpětím stromu je však Ω (n α (k)), kde α je inverzní Ackermannova funkce, ještě slabší hranice než pro k-nastavený problém. Pro obecnější matroidy, Dey's Ó(nk^1/3) horní mez má odpovídající dolní mez.^[9]

Poznámky

Reference

externí odkazy

• Poloviční čáry a k-sady, Jeff Erickson
• Projekt Otevřené problémy, problém 7: k-sady