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