192 KB15 KB197720262006Cabello, SergioDeVos, MattMohar, Bojanštevilka:3letnik:30str. 289-293ISSN:0350-5596COBISSID:20378919URN:URN:NBN:SI:doc-T00BLQRAenSlovensko društvo InformatikaInformatica (Ljubljana)gostota točkkombinatorična geometrijaverjetnostExpected case for projecting points|Consider a set of ?$n$? points in the plane with the property that any pair of points is at least at distance one. We study the expected concentration of the point set after projecting it onto a random graduated line. There is a lower bound of ?$\Omega(\sqrt{n\log n})$? given by Matoušek, and we provide an upper bound of ?$O(n^{2/3})$?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 ?$\Omega(\sqrt{n\log n})$? projiciranimi točkami. V prispevku pa je dokazana zgornja meja ?$O(n^{2/3})$? za pričakovano vrednostTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaSlovensko društvo Informatika