Article View: comp.theory
Article #1864Re: looking for an algorithm...
From: Joseph O'Rourke
Date: Tue, 26 Jan 1993 18:27
Date: Tue, 26 Jan 1993 18:27
16 lines
957 bytes
957 bytes
In article <279@enstb.enst-bretagne.fr> dezan@enstb.enst-bretagne.fr writes:
>I am looking for an algorithm which can separate n convex polyhedral domains
>(each one from others) with a minimal number of hyperplans.
>Does such an algorithm exist?
>What about its complexity?
Most variations are NP-complete:
@article{m-cps-88
, author = "N. Megiddo"
, title = "On the complexity of polyhedral separability"
, journal = "Discrete Comput. Geom."
, volume = 3
, year = 1988
, pages = "325--337"
}
Technical Details
Message-ID:
<1993Jan26.182740.28632@sophia.smith.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!news.mtholyoke.edu!news.smith.edu!orourkeReferences:
<279@enstb.enst-bretagne.fr>Show Full Headers
Complete Article Headers
Newsgroups: comp.theory Path: arc1-ca.pugleaf.net!sparky!uunet!news.mtholyoke.edu!news.smith.edu!orourke From: orourke@sophia.smith.edu (Joseph O'Rourke) Subject: Re: looking for an algorithm... Message-ID: <1993Jan26.182740.28632@sophia.smith.edu> Keywords: convex polyhedral domain Organization: Smith College, Northampton, MA, US References: <279@enstb.enst-bretagne.fr> Date: Tue, 26 Jan 1993 18:27:40 GMT Lines: 16