Diameter of Polyhedra: Limits of Abstraction

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.


Published in:
25th Annual ACM Symposium on Computational Geometry (SoCG'09), 386-392
Presented at:
25th Annual ACM Symposium on Computational Geometry (SoCG'09), Aarhus, Denmark, June 8-10, 2009
Year:
2009
ISBN:
978-1-60558-501-7
Keywords:
Laboratories:




 Record created 2009-03-17, last modified 2018-09-13

n/a:
Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)