Fast stabbing of boxes in high dimensions

作     者：Nielsen, F 

作者机构：INRIA F-06902 Sophia Antipolis France Univ Nice F-06304 Nice France Univ Tokyo Tokyo Japan Univ Nice Sophia Antipolis Valrose France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2000年第246卷第1-2期

页      面：53-72页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：computational geometry geometric combinatorial optimization output-sensitive algorithms 

摘      要：We present in this paper a simple yet efficient algorithm for stabbing a set F of n axis-parallel boxes in d-dimensional space with c(F) points in output-sensitive lime O(dn log c(F)) and linear space. Let c*(F) and b*(F) be, respectively, the minimum number of points required to stab F and the maximum number of pairwise disjoint boxes of F. We prove that b*(F) less than or equal to c*(F) less than or equal to c(F) less than or equal to b*(F)(1+log(2) b*(F))(d-1). Since finding a minimal set of c*(F) points is NP-complete as soon as d 1, we obtain a fast precision-sensitive heuristic for stabbing. F whose quality does not depend on the input size, In the case of congruent or constrained isothetic boxes, our algorithm reports, respectively, c(F)less than or equal to 2(d-1)b*(F) and c(F)= O-d(b*(F)) stabbing points, Moreover, we show that the bounds we get on c(F) are asymptotically tight and corroborate our results with some experiments. We also describe an optimal output-sensitive algorithm for findings a minimal-size optimal stabbing point-set of intervals. Finally, we conclude with insights for further research. (C) 2000 Elsevier Science B.V. All rights reserved.