Linear Binary Space Partitions and the Hierarchy of Object Classes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F03%3A00008369" target="_blank" >RIV/00216224:14330/03:00008369 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Linear Binary Space Partitions and the Hierarchy of Object Classes

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

Linear Binary Space Partitions and the Hierarchy of Object Classes

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GV201%2F98%2FK041" target="_blank" >GV201/98/K041: HCILAB - Laboratoř interakcí člověka s počítačem</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2003

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Abstracts for the 15th Canadian Conference on Computational Geometry

ISBN

—

ISSN

—

e-ISSN

—

Počet stran výsledku

4

Strana od-do

64-67

Název nakladatele

Dalhousie University

Místo vydání

Halifax, Canada

Místo konání akce

Halifax

Datum konání akce

1. 1. 2003

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—