It is well known that in practice, a substantial difference in run-time between algorithms for testing intersection of a line segment with aligned or oriented bounding boxes (in computer graphics parlance AABB/OBB) does exist. Nevertheless, I wonder if anybody has ever tried to find a lower bound on the run-time for a deterministic algorithm for either problem and found that this lower bound is actually different.I have been conducting several searches on both Scholar and naked Google and either (1) I don't know how to formulate the question in a format such that Google algorithms return a relevant answer, or indeed (2) nobody has looked into this problem. I do think that (1) is way more likely than (2). So I would appreciate if anybody here is aware of a result like the one I am trying to find, or if it has been discussed in some (formal) way that I can cite, could provide me with some pointers.Thanks!
Inherent complexity of testing line segment intersections with aligned and oriented bounding boxes?
complexity theory;reference request;computational geometry