home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / theory / 2930 < prev    next >
Encoding:
Text File  |  1993-01-27  |  930 b   |  28 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!news.mtholyoke.edu!news.smith.edu!orourke
  3. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  4. Subject: Re: looking for an algorithm...
  5. Message-ID: <1993Jan26.182740.28632@sophia.smith.edu>
  6. Keywords: convex polyhedral domain
  7. Organization: Smith College, Northampton, MA, US
  8. References: <279@enstb.enst-bretagne.fr>
  9. Date: Tue, 26 Jan 1993 18:27:40 GMT
  10. Lines: 16
  11.  
  12. In article <279@enstb.enst-bretagne.fr> dezan@enstb.enst-bretagne.fr writes:
  13. >I am looking for an algorithm which can separate n convex polyhedral domains
  14. >(each one from others) with a minimal number of hyperplans.
  15. >Does such an algorithm exist?
  16. >What about its complexity?
  17.  
  18. Most variations are NP-complete:
  19.  
  20. @article{m-cps-88
  21. , author =      "N. Megiddo"
  22. , title =       "On the complexity of polyhedral separability"
  23. , journal =     "Discrete Comput. Geom."
  24. , volume =      3
  25. , year =        1988
  26. , pages =       "325--337"
  27. }
  28.