FINDING A LINE OF SIGHT THRU BOXES IN d-SPACE IN LINEAR TIME
Nimrod Megiddo, Nimrod Mcgiddo · 2005
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 all 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. Finding a Line of Sight Thru Boxes in d-Space in Linear Time