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 vrednost.

Pravice

URN

URN:NBN:SI:DOC-T00BLQRA

COBISSID

20378919

Objavljeno

21.04.2016

Metapodatki

Citiranje

APA:

Cabello, Sergio, DeVos, Matt, Mohar, Bojan (2006). Expected case for projecting points. Informatica (Ljubljana), letnik 30, številka 3, str. 289-293. URN:NBN:SI:DOC-T00BLQRA from http://www.dlib.si

MLA:

Cabello, Sergio, DeVos, Matt, Mohar, Bojan. "Expected case for projecting points." Informatica (Ljubljana) letnik 30. številka 3 (2006) str. 289-293.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-T00BLQRA>

Informatica
1977-
(Zbirni zapis)