zhu@khaki.asd.sgi.com (Benjamin Zhu) (05/30/91)
Does anyone have a program to determine if the intersection of n 3D half-spaces is empty? I did some scratches, and concluded that it can be done within O(n^3) time. I am not sure, however, if the complexity can be further reduced, and I will be extremely interested if somebody can prove that a complexity of O(n^2) or O(log(n)*n^2) can be achieved. Since even a O(n^3) implementation will be really messy when taking degenerated cases into account, I would rather use existing code if it is available. Please respond by email. Thanks in advance. Ben zhu@graphack.asd.sgi.com