Skip navigation
SuUB logo
DSpace logo

  • Home
  • Institutions
    • University of Bremen
    • City University of Applied Sciences
    • Bremerhaven University of Applied Sciences
  • Sign on to:
    • My Media
    • Receive email
      updates
    • Edit Account details

Citation link: http://nbn-resolving.de/urn:nbn:de:gbv:46-00104422-11
00104422-1.pdf
OpenAccess
 
copyright

The Convex Hull Problem in Practice : Improving the Running Time of the Double Description Method


File Description SizeFormat
00104422-1.pdf1.53 MBAdobe PDFView/Open
Other Titles: Das Problem der konvexen Hülle in der Praxis
Authors: Genov, Blagoy 
Supervisor: Peleska, Jan
1. Expert: Peleska, Jan
2. Expert: Frese, Udo
Abstract: 
The double description method is a simple but widely used algorithm for computation of extreme points in polyhedral sets. One key aspect of its implementation is the question of how to efficiently test extreme points for adjacency. In this dissertation, two significant contributions related to adjacency testing are presented. First, the currently used data structures are revisited and various optimizations are proposed. Empirical evidence is provided to demonstrate their competitiveness. Second, a new adjacency test is introduced. It is a refinement of the well known algebraic test featuring a technique for avoiding redundant computations. Its correctness is formally proven. Its superiority in multiple degenerate scenarios is demonstrated through experimental results. Parallel computation is one further aspect of the double description method covered in this work. A recently introduced divide-and-conquer technique is revisited and considerable practical limitations are demonstrated.
Keywords: convex polyhedra, convex hull, extreme ray enumeration, vertex enumeration, facet enumeration
Issue Date: 28-Jan-2015
Type: Dissertation
URN: urn:nbn:de:gbv:46-00104422-11
Institution: Universität Bremen 
Faculty: FB3 Mathematik/Informatik 
Appears in Collections:Dissertationen

  

Page view(s)

46
checked on Jan 27, 2021

Download(s)

23
checked on Jan 27, 2021

Google ScholarTM

Check


Items in Media are protected by copyright, with all rights reserved, unless otherwise indicated.

Legal notice -Feedback -Data privacy
Media - Extension maintained and optimized by Logo 4SCIENCE