Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
This paper examines the complexity of several geometric problems due to unbounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by unit balls, and (iii) minimum number of lines to hit a set of balls. Each of these problems is proven not to have a polynomial approximation scheme unless P = NP. Specific lower bounds on the error ratios attainable in polynomial time are given, assuming P ≠ NP. In particular, it is shown that covering by two cubes is in P while covering by three cubes is NP-complete. © 1990, Academic Press Limited. All rights reserved.
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
T. Graham, A. Afzali, et al.
Microlithography 2000
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering