TY - GEN
T1 - Algorithms for two-box covering
AU - Arkin, Esther M.
AU - Barequet, Gill
AU - Mitchell, Joseph S.B.
PY - 2006
Y1 - 2006
N2 - We study the problem of covering a set of points or polyhedra in R 3 with two axis-aligned boxes in order to minimize a function of the measures of the two boxes, such as the sum or the maximum of their volumes. This 2-box cover problem arises naturally in the construction of bounding volume hierarchies, as well as in shape approximation and clustering. Existing algorithms solve the min-max version of the exact problem in quadratic time. Our results are more general, addressing min-max, min-sum and other versions. Our results give the first approximation schemes for the problem, which run in nearly linear time, as well as some new exact algorithms. We give (1 + ε)-approximation algorithms for minimizing the maximum or sum of volumes (or surface areas, diameters, widths, or girths) of the two boxes in R 3. We investigate also the problem of computing balanced coverings, in which each box covers at least a fraction of the input objects, and we discuss the application to constructing provably-good bounding volume hierarchies of polyhedra. We also generalize our results to higher dimensions.
AB - We study the problem of covering a set of points or polyhedra in R 3 with two axis-aligned boxes in order to minimize a function of the measures of the two boxes, such as the sum or the maximum of their volumes. This 2-box cover problem arises naturally in the construction of bounding volume hierarchies, as well as in shape approximation and clustering. Existing algorithms solve the min-max version of the exact problem in quadratic time. Our results are more general, addressing min-max, min-sum and other versions. Our results give the first approximation schemes for the problem, which run in nearly linear time, as well as some new exact algorithms. We give (1 + ε)-approximation algorithms for minimizing the maximum or sum of volumes (or surface areas, diameters, widths, or girths) of the two boxes in R 3. We investigate also the problem of computing balanced coverings, in which each box covers at least a fraction of the input objects, and we discuss the application to constructing provably-good bounding volume hierarchies of polyhedra. We also generalize our results to higher dimensions.
KW - Exact and approximate algorithms
UR - https://www.scopus.com/pages/publications/33748079793
U2 - 10.1145/1137856.1137923
DO - 10.1145/1137856.1137923
M3 - Conference contribution
AN - SCOPUS:33748079793
SN - 1595933409
SN - 9781595933409
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 459
EP - 467
BT - Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PB - Association for Computing Machinery
T2 - 22nd Annual Symposium on Computational Geometry 2006, SCG'06
Y2 - 5 June 2006 through 7 June 2006
ER -