Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!lll-winken!sun-barr!ames!sgi!zhu@khaki.asd.sgi.com
From: zhu@khaki.asd.sgi.com (Benjamin Zhu)
Newsgroups: comp.graphics
Subject: Emptiness of intersection of n half-spaces
Message-ID: <106866@sgi.sgi.com>
Date: 30 May 91 01:55:04 GMT
Sender: guest@sgi.sgi.com
Distribution: ca
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 12

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