Thread View: comp.theory
2 messages
2 total messages
Started by Catherine Dezan
Tue, 26 Jan 1993 11:09
looking for an algorithm...
Author: Catherine Dezan
Date: Tue, 26 Jan 1993 11:09
Date: Tue, 26 Jan 1993 11:09
10 lines
783 bytes
783 bytes
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? Thank you very much in advance for any information. Catherine Dezan. email : dezan@enstb.enst-bretagne.fr
Re: looking for an algorithm...
Author: 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"
}
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads