Publication

Diameter of Polyhedra: Limits of Abstraction

2010
Journal Articles

Abstract

We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Even if this abstraction is more general than other abstractions previously studied in the literature, known upper bounds on the diameter of polyhedra continue to hold here. On the other hand, we show that this abstraction has its limits by providing an almost quadratic lower bound.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2010
Journal Articles

Abstract

Official source

Related concepts (32)

Polyhedron

In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is a polyhedron that bounds a convex set. Every convex polyhedron can be constructed as the convex hull of its vertices, and for every finite set of points, not all on the same plane, the convex hull is a convex polyhedron. Cubes and pyramids are examples of convex polyhedra. A polyhedron is a 3-dimensional example of a polytope, a more general concept in any number of dimensions.

List of uniform polyhedra

In geometry, a uniform polyhedron is a polyhedron which has regular polygons as faces and is vertex-transitive (transitive on its vertices, isogonal, i.e. there is an isometry mapping any vertex onto any other). It follows that all vertices are congruent, and the polyhedron has a high degree of reflectional and rotational symmetry. Uniform polyhedra can be divided between convex forms with convex regular polygon faces and star forms. Star forms have either regular star polygon faces or vertex figures or both.

Quasiregular polyhedron

In geometry, a quasiregular polyhedron is a uniform polyhedron that has exactly two kinds of regular faces, which alternate around each vertex. They are vertex-transitive and edge-transitive, hence a step closer to regular polyhedra than the semiregular, which are merely vertex-transitive. Their dual figures are face-transitive and edge-transitive; they have exactly two kinds of regular vertex figures, which alternate around each face. They are sometimes also considered quasiregular.

Related publications (2)

Diameter of Polyhedra: Limits of Abstraction

Chat with Graph Search

The lexico-smallest representation of convex polyhedra

On canonical representations of convex polyhedra