Linear size binary space partitions for uncluttered scenes

    Research output: Contribution to journalArticleAcademicpeer-review

    50 Citations (Scopus)


    We describe a new and simple method for constructing binary space partitions (BSPs) in arbitrary dimensions. We also introduce the concept of uncluttered scenes, which are scenes with a certain property that we suspect many realistic scenes exhibit, and we show that our method constructs a BSP of size O(n) for an uncluttered scene consisting of n objects. The construction time is O(n log n) . Because any set of disjoint fat objects is uncluttered, our result implies an efficient method to construct a linear size BSP for fat objects. We use our BSP to develop a data structure for point location in uncluttered scenes. The query time of our structure is O( log n) , and the amount of storage is O(n) . This result can in turn be used to perform range queries with not-too-small ranges in scenes consisting of disjoint fat objects or, more generally, in so-called low-density scenes.
    Original languageEnglish
    Pages (from-to)353-366
    Issue number3
    Publication statusPublished - 2000


    Dive into the research topics of 'Linear size binary space partitions for uncluttered scenes'. Together they form a unique fingerprint.

    Cite this