The following problem is addressed. Given a set of rectangular boxes with edges parallel to the axes in a Euclidean space, find a straight line that intersects the boxes, or conclude that no such line exists. An algorithm is presented which solves the problem in linear time for any fixed dimension of the space.
By: Nimrod Megiddo
Published in: RJ10018 in 1996
This Research Report is not available electronically. Please request a copy from the contact listed below. IBM employees should contact ITIRC for a copy.
Questions about this service can be mailed to reports@us.ibm.com .