2003
Linear Binary Space Partitions and the Hierarchy of Object Classes
TOBOLA, Petr a Karel NECHVÍLEZákladní údaje
Originální název
Linear Binary Space Partitions and the Hierarchy of Object Classes
Autoři
TOBOLA, Petr (203 Česká republika, garant) a Karel NECHVÍLE (203 Česká republika)
Vydání
1. vyd. Halifax, Canada, Abstracts for the 15th Canadian Conference on Computational Geometry, od s. 64-67, 4 s. 2003
Nakladatel
Dalhousie University
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Kanada
Utajení
není předmětem státního či obchodního tajemství
Kód RIV
RIV/00216224:14330/03:00008369
Organizační jednotka
Fakulta informatiky
Klíčová slova anglicky
BSP; Tree; Partitioning; Object; Class; Hierarchy
Změněno: 2. 12. 2003 15:24, Mgr. Petr Tobola, Ph.D.
Anotace
V originále
We consider the problem of constructing binary space partitions for the set P of d-dimensional objects in d-dimensional space. There are several classes of objects defined for such settings, which support design of effective algorithms. We extend the existing the de Berg hierarchy of classes by the definition of new classes derived from that one and we show desirability of such an extension. Moreover we propose a new algorithm, which works on generalized $\lambda$-low density scenes (defined in this paper) and provides BSP tree of linear size. The tree can be constructed in $O(n \log^2 n)$ time and space, where n is the number of objects. Moreover, we can trade-off between size and balance of the BSP tree fairly simply.
Návaznosti
| GV201/98/K041, projekt VaV |
| ||
| MSM 143300003, záměr |
|