conference paper
Diameter of Polyhedra: Limits of Abstraction
2009
25th Annual ACM Symposium on Computational Geometry (SoCG'09)
We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Although this abstraction is simpler than other abstractions that were previously studied in the literature, the best 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 a superlinear lower bound.
Type
conference paper
Web of Science ID
WOS:000267982900052
Date Issued
2009
Published in
25th Annual ACM Symposium on Computational Geometry (SoCG'09)
ISBN of the book
978-1-60558-501-7
Start page
386
End page
392
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Event name | Event place | Event date |
Aarhus, Denmark | June 8-10, 2009 | |
Available on Infoscience
March 17, 2009
Use this identifier to reference this record