Linear Size Binary Space Partitions for Uncluttered Scenes |
| |
Authors: | M. de Berg |
| |
Affiliation: | (1) Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands. markdb@cs.uu.nl., NL |
| |
Abstract: | 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. Received December 11, 1997; revised May 9, 1998. |
| |
Keywords: | . Computational geometry Binary space partitions Realistic input models Fatness linebreak[4] Unclutteredness. |
本文献已被 SpringerLink 等数据库收录! |
|