Publication

DYNAMIC PARTITION TREES

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

Research output: Contribution to journalArticleAcademicpeer-review

  • H SCHIPPER
  • MH OVERMARS

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.

Original languageEnglish
Pages (from-to)421-436
Number of pages16
JournalBit
Volume31
Issue number3
Publication statusPublished - 1991

    Keywords

  • SEARCH

ID: 6299565