Publication

DYNAMIC PARTITION TREES

SCHIPPER, H. & OVERMARS, MH., 1991, In : Bit. 31, 3, p. 421-436 16 p.

Research output: Contribution to journalArticleAcademicpeer-review

APA

SCHIPPER, H., & OVERMARS, MH. (1991). DYNAMIC PARTITION TREES. Bit, 31(3), 421-436.

Author

SCHIPPER, H ; OVERMARS, MH. / DYNAMIC PARTITION TREES. In: Bit. 1991 ; Vol. 31, No. 3. pp. 421-436.

Harvard

SCHIPPER, H & OVERMARS, MH 1991, 'DYNAMIC PARTITION TREES', Bit, vol. 31, no. 3, pp. 421-436.

Standard

DYNAMIC PARTITION TREES. / SCHIPPER, H; OVERMARS, MH.

In: Bit, Vol. 31, No. 3, 1991, p. 421-436.

Research output: Contribution to journalArticleAcademicpeer-review

Vancouver

SCHIPPER H, OVERMARS MH. DYNAMIC PARTITION TREES. Bit. 1991;31(3):421-436.


BibTeX

@article{9bc55335dd03493b960ebfe3684c8383,
title = "DYNAMIC PARTITION TREES",
abstract = "In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time of O(log2 n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set of n triangles that runs in time 0(nlog n + n.kg-gamma) where gamma = log2 ((1 + square-root 5)/2) almost-equal-to 0.695 and k is the size of the visibility map obtained.",
keywords = "SEARCH",
author = "H SCHIPPER and MH OVERMARS",
year = "1991",
language = "English",
volume = "31",
pages = "421--436",
journal = "Bit numerical mathematics",
issn = "0006-3835",
number = "3",

}

RIS

TY - JOUR

T1 - DYNAMIC PARTITION TREES

AU - SCHIPPER, H

AU - OVERMARS, MH

PY - 1991

Y1 - 1991

N2 - In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time of O(log2 n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set of n triangles that runs in time 0(nlog n + n.kg-gamma) where gamma = log2 ((1 + square-root 5)/2) almost-equal-to 0.695 and k is the size of the visibility map obtained.

AB - In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time of O(log2 n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set of n triangles that runs in time 0(nlog n + n.kg-gamma) where gamma = log2 ((1 + square-root 5)/2) almost-equal-to 0.695 and k is the size of the visibility map obtained.

KW - SEARCH

M3 - Article

VL - 31

SP - 421

EP - 436

JO - Bit numerical mathematics

JF - Bit numerical mathematics

SN - 0006-3835

IS - 3

ER -

ID: 6299565