ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

Halfspace range search: An algorithmic application ofk-sets (1986)

Chazelle, B. ; Preparata, F. P.

Springer

Discrete & computational geometry 1 (1986), S. 83-93

add to mindlist on the mindlist

Details

ISSN: 1432-0444

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract Given a fixed setS ofn points inE 3 and a query planeπ, the halfspace range search problem asks for the retrieval of all points ofS on a chosen side ofπ. We prove that withO(n(logn)8 (loglogn)4) storage it is possible to solve this problem inO(k+logn) time, wherek is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number ofj-sets (j=1, ...,k) realized by a set ofn points inE 3 isO(nk 5); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF02187685

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit