Heilbronnův trojúhelníkový problém - Heilbronn triangle problem

Řešení úlohy Heilbronnova trojúhelníku pro šest bodů v jednotkovém čtverci. Tyto body tvoří trojúhelníky čtyř různých tvarů, s minimální plochou 1/8, co největší pro šest bodů ve čtverci. Toto řešení je afinní transformace a pravidelný šestiúhelník ale větší počet bodů má řešení, která zahrnují vnitřní body čtverce.

v diskrétní geometrie a teorie nesrovnalostí, Heilbronnův trojúhelníkový problém je problém umístit body do oblasti v rovině, aby se tomu zabránilo trojúhelníky malých plocha. Je pojmenován po Hans Heilbronn, SZO domnělý před rokem 1950 je tato nejmenší oblast trojúhelníku nutně nanejvýš nepřímo úměrné do náměstí počtu bodů. Ukázalo se, že Heilbronnova domněnka byla falešná, ale asymptotický růst rychlost oblasti minimálního trojúhelníku zůstává neznámá.

Definice

Problém lze definovat v pojmech jakýkoli kompaktní soubor D v letadle s nenulovou oblastí, jako je jednotka čtverec nebo jednotka disku. Li S je sada n body D, pak každé tři body S určit trojúhelník (pravděpodobně zdegenerovaný, s nulovou oblastí). Nechť Δ (S) označíme minimum ploch těchto trojúhelníků a nechme Δ (n) (pro celé číslo.) n ≥ 3) označují supremum z hodnot Δ (S).

Otázkou, kterou položil Heilbronn, bylo dát výraz nebo odpovídat asymptoticky horní a dolní mez, pro Δ (n). To znamená, že cílem je najít a funkce F, popsaný a uzavřený výraz a konstanty C1 a C2, tak, že pro všechny n,

.

Ve smyslu velká O notace, levá nerovnost může být zapsána jako Δ (n) = Ω (F(n)), pravou nerovnost lze zapsat jako Δ (n) = Ó(F(n)) a oba mohou být společně zapsány jako Δ (n) = Θ (F(n)). Tvar a plocha D může ovlivnit přesné hodnoty Δ (n), ale pouze konstantním faktorem, takže pro jeho asymptotickou rychlost růstu nejsou důležité.

Heilbronnova domněnka a konstrukce s dolní hranicí

Heilbronn si to myslel

Tak jako Paul Erdős ukázáno, není možná žádná menší vazba: když n je prvočíslo, soubor n body (i, i2 modn) na n × n celočíselná mřížka mít žádné tři kolineární body, a tedy do Pickův vzorec každý z trojúhelníků, které tvoří, má plochu alespoň 1/2. Když je tato sada bodů mřížky zmenšena na jednotkový čtverec, tvoří sadu bodů, jejichž nejmenší plocha trojúhelníku je alespoň úměrná 1 /n2, odpovídající Heilbronnově domnělé horní hranici.[1]Li n není prvočíslo, pak je podobná konstrukce využívající další prvočíslo větší než n dosahuje stejné asymptotické dolní meze.

Komlós, Pintz a Szemerédi (1982) nakonec vyvrátil Heilbronnovu domněnku tím, že našel sady bodů, jejichž nejmenší plocha trojúhelníku roste asymptoticky jako

[2]

Horní hranice

Triviálně, buď triangulace the konvexní obal dané množiny bodů S nebo výběrem po sobě jdoucích trojných bodů v seřazeném pořadí X- souřadnice, je možné ukázat, že každá množina bodů obsahuje malý trojúhelník, jehož plocha je maximálně nepřímo úměrnán. Roth (1951) byl první, kdo dokázal netriviální horní mez na Δ (n) formuláře[1]

Nejlépe známá dosud známá forma má formu

pro nějakou konstantu C, prokázáno Komlós, Pintz a Szemerédi (1981).[3]

Konkrétní tvary a čísla

Goldberg (1972) zkoumala optimální uspořádání n bodů ve čtverci, pro n až 16.[4] Goldbergovy konstrukce až pro šest bodů leží na hranici čtverce a jsou umístěny tak, aby tvořily afinní transformace vrcholů a pravidelný mnohoúhelník. Pro větší hodnoty n, Comellas & Yebra (2002) vylepšil Goldbergovy hranice a pro tyto hodnoty zahrnuje řešení body uvnitř čtverce.[5] Ukázalo se, že tyto konstrukce jsou optimální až pro sedm bodů.[6]

Variace

Existuje mnoho variant tohoto problému, včetně případu rovnoměrně náhodného souboru bodů, pro které argumenty vycházejí buď Kolmogorovova složitost nebo Poissonova aproximace ukázat, že očekávaná hodnota minimální plochy je nepřímo úměrný krychli počtu bodů.[7][8] Variace zahrnující objem výškových jednoduchosti byly také studovány.[9]

Viz také

  • Sada Danzer, sada bodů, která se vyhýbá prázdným trojúhelníkům velké plochy

Reference

  1. ^ A b Roth, K.F. (1951), „O problému Heilbronnu“, Journal of the London Mathematical Society, 26 (3): 198–204, doi:10.1112 / jlms / s1-26.3.198.
  2. ^ Komlós, J.; Pintz, J.; Szemerédi, E. (1982), „Spodní hranice Heilbronnova problému“, Journal of the London Mathematical Society, 25 (1): 13–24, doi:10.1112 / jlms / s2-25.1.13, PAN  0645860.
  3. ^ Komlós, J.; Pintz, J.; Szemerédi, E. (1981), „O Heilbronnově trojúhelníkovém problému“, Journal of the London Mathematical Society, 24 (3): 385–396, doi:10.1112 / jlms / s2-24.3.385, PAN  0635870.
  4. ^ Goldberg, Michael (1972), „Maximalizace nejmenšího trojúhelníku od firmy n body ve čtverci ", Matematický časopis, 45: 135–144, doi:10.2307/2687869, JSTOR  2687869, PAN  0296816.
  5. ^ Comellas, Francesc; Yebra, J. Luis A. (2002), „Nové dolní meze pro čísla Heilbronnu“, Electronic Journal of Combinatorics, 9 (1): R6, PAN  1887087.
  6. ^ Zeng, Zhenbing; Chen, Liangyu (2011), „Na Heilbronnu optimální konfigurace sedmi bodů ve čtverci“, Automatický odpočet v geometrii, Poznámky k přednášce ve Výpočtu. Sci., 6301, Heidelberg: Springer, s. 196–224, doi:10.1007/978-3-642-21046-4_11, PAN  2805061.
  7. ^ Jiang, Tao; Li, Ming; Vitányi, Paul (2002), „Průměrná oblast trojúhelníků typu Heilbronn“, Náhodné struktury a algoritmy, 20 (2): 206–219, arXiv:matematika / 9902043, doi:10.1002 / rsa.10024, PAN  1884433.
  8. ^ Grimmett, G.; Janson, S. (2003), „Na nejmenších trojúhelnících“, Náhodné struktury a algoritmy, 23: 206–223.
  9. ^ Lefmann, Hanno (2008), „Rozdělení bodů v roce 2006 d rozměry a velké k-bodové jednoduchosti ", Diskrétní a výpočetní geometrie, 40 (3): 401–413, doi:10.1007 / s00454-007-9041-r, PAN  2443292.

externí odkazy