Fast stabbing of boxes in high dimension
โ
Frank Nielsen
๐
Article
๐
2000
๐
Elsevier Science
๐
English
โ 382 KB
We present in this paper a simple yet e cient algorithm for stabbing a set S of n axisparallel boxes in d-dimensional space with c(S) points in output-sensitive time O(dn log c(S)) and linear space. Let c \* (S) and b \* (S) be, respectively, the minimum number of points required to stab S and the m