Unions of Fat Convex Polytopes Have Short Skeletons |
| |
Authors: | Boris Aronov Mark de Berg |
| |
Institution: | 1.Department of Computer Science and Engineering,Polytechnic Institute of NYU,Brooklyn,USA;2.Department of Computing Science,TU Eindhoven,Eindhoven,The Netherlands |
| |
Abstract: | The skeleton of a polyhedral set is the union of its edges and vertices. Let \(\mathcal {P}\) be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f max be the maximum complexity of any face of a polytope in \(\mathcal {P}\). We prove that the total length of the skeleton of the union of the polytopes in \(\mathcal {P}\) is at most O(α(n)?log? n?logf max) times the sum of the skeleton lengths of the individual polytopes. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|