Expected case for projecting points - Cabello, Sergio (Informatica (Ljubljana), 2006)
Za dano ?$n$?-terico točk v ravnini, ki so med seboj na razdalji vsaj 1, je obravnavan problem projekcije na slučajno premico ?$L$?, pri čemer želimo, da ima vsak interval dolžine 1 na ?$L$? čim manj projiciranih točk. Znano je, da obstajajo primeri točk, kjer vsaka projekcija vsebuje enotski interval z ?$Ω(\sqrt{n\log n})$? projiciranimi točkami. V prispevku pa je dokazana zgornja meja ?$O(n^{2/3})$? za pričakovano vrednost.
Keywords: kombinatorična geometrija; verjetnost; gostota točk