From: Jeff Erickson Newsgroups: sci.math Subject: Re: Must polytopes be convex? Date: Mon, 23 Mar 1998 23:20:28 -0500 Jonathan R Shewchuk wrote: > What is the precise meaning of "polytope," and precisely how does it > differ from "polyhedron"? "Polytope" is usually a synonym for "convex polytope": the convex hull of a finite set of points, or equivalently, the bounded intersection of a finite number of halfspaces. There are (at least) three conventional meanings for "polyhedron", with some variants. 1. possibly non-convex union of finitely many convex polytopes (a) simply connected (b) connected but not necessary simply connected (c) not necessarily connected 2. possibly unbounded intersection of finitely many halfspaces 3. three-dimensional convex polytope (relatively rare, at least in computational geometry) It wouldn't surprise me to see someone using a combination of the first two definitions -- a ((simply?) connected?) boolean combination of finitely many halfspaces, neither necessarily bounded nor necessarily convex. A few papers refer to simple (ie, non-self-intersecting) polyhedra, so there must be a fourth even more general definition that allows self-intersections. This use of "simple" is really confusing, since "simple polytope" usually means a convex polytope in which every vertex lies on d facets. Yuck! Unfortunately, the exact choice of meaning usually has to be inferred from context. > Can a polytope be nonconvex, or is "polytope" strictly defined to > denote only convex objects? Most readers will probably assume that polytopes are convex unless you say otherwise. Unless you need to make a distinction between bounded/unbounded or simple/self-intersecting, I suggest sticking to "polyhedron" for nonconvex objects. -- Jeff Erickson Center for Geometric Computing jeffe@cs.duke.edu Department of Computer Science http://www.cs.duke.edu/~jeffe Duke University ============================================================================== From: Robin Chapman Newsgroups: sci.math Subject: Re: Must polytopes be convex? Date: Tue, 24 Mar 1998 02:10:28 -0600 In article <6f6i41$5s9$1@goldenapple.srv.cs.cmu.edu>, jrs@cs.cmu.edu (Jonathan R Shewchuk) wrote: > > What is the precise meaning of "polytope," and precisely how does it > differ from "polyhedron"? To me a polyhedron is a three-dimensional thing and a polytope is an n-dimesnional thing, but others disagree. > For instance, the terms "polygon" and "polyhedron" are commonly used to > denote nonconvex objects. Can a polytope be nonconvex, or is "polytope" > strictly defined to denote only convex objects? To me a polytope may by non-convex, but others disagree. > I note that geometric texts are not always helpful in this question. > For instance, several authors I have consulted define "polyhedron" as > an intersection of half-spaces, despite the fact that the term is > frequently used in reference to nonconvex objects. Hence, the fact > that several authors define "polytope" the same way does not itself > constitute useful evidence. Various authors have various conventions. I suspect you mean that a "polyhedron" is a finite intersection of half spaces, as any closed or open convex set is an intersection of half-spaces. I would never call an unbounded set a polyhedron, but others would. Conclusion: there is no consensus on the use of these terms, so one had better get used to that. Robin Chapman -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading ============================================================================== From: eppstein@euclid.ics.uci.edu (David Eppstein) Newsgroups: sci.math Subject: Re: Carthesian Polyhedron Descriptions Date: 24 Nov 1998 13:18:30 -0800 In <73ep5j$u4a$1@nnrp1.dejanews.com> Robin Chapman writes: > polygon : 2-dimensional > polyhedron : 3-dimensional > polytope : n-dimensional That's the way I use those words, too. But some other people use both "polyhedron" and "polytope" to apply to shapes in any dimension, with one of the two words meaning a convex hull of a finite set of points (i.e. a bounded convex flat-sided thing) and the other word to mean an intersection of finitely many halfspaces (i.e. a possibly unbounded convex flat-sided thing). As you can probably tell, I can't keep track of which word is supposed to refer to which type of object. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== From: Jeff Erickson Newsgroups: sci.math Subject: Re: Carthesian Polyhedron Descriptions Date: Tue, 24 Nov 1998 16:12:06 -0600 David Eppstein wrote: > ...some other people use both "polyhedron" and "polytope" to apply to > shapes in any dimension, with one of the two words meaning a convex hull > of a finite set of points (i.e. a bounded convex flat-sided thing) and > the other word to mean an intersection of finitely many halfspaces > (i.e. a possibly unbounded convex flat-sided thing). As you can > probably tell, I can't keep track of which word is supposed to refer to > which type of object. Polytopes are bounded; polyhedra might not be. Polytopes are bounded polyhedra. Still other people use "polytope" to mean a bounded convex flat-sided thingie, and "polyhedron" to mean a bounded not-necessarily-convex flat-sided thingie -- so polytopes are convex polyhedra. These people should be shot. -- Jeff Erickson jeffe@cs.uiuc.edu Computer Science Department http://www.uiuc.edu/ph/www/jeffe University of Illinois, Urbana-Champaign