In this paper we consider the followign covering problem. Given a set S of n points in d-dimensional space, d≥2, find two axis-parallel boxes that together cover the set S such that the measure iof the largest box is minimized, where the measure is a monotone function of the box. We present a simple algorithm for finding boxes in O(n log n＋n~d-1) time and and O(n) space.
展开▼
机译：在本文中，我们考虑了后续覆盖问题。给定d维空间中d个点的集合S，d≥2，找到两个轴平行的盒子，它们一起覆盖了集合S，从而最大盒子的度量i最小化，其中度量是盒子的单调函数。我们提出了一种在O（n log n ＋ n〜d-1）时间和O（n）空间中寻找盒子的简单算法。
展开▼
