Summary
2007 International Symposium on Nonlinear Theory and its Applications
2007
Session Number:19AM1-A
Session:
Number:19AM1-A-2
A Primal-Dual Beneath-Beyond Method
Yuzo Ohta, Masashi Tsumura,
pp.353-356
Publication Date:2007/9/16
Online ISSN:2188-5079
DOI:10.34385/proc.41.19AM1-A-2
Summary:
The purpose of this paper is to propose an improved primal-dual beneath?beyond method to solve dynamic convex hull problem in d-dimensional space efficiently. The traditional beneath?beyond method requires the whole data of its faces and their inclusion relations. However, in the application of the dynamic convex hull problem, we usually do not need data of all faces. When the dimension d becomes large, then the computing time to maintain these unnecessary data becomes very large. In this respect, we propose a method which need data of facets and subfacets, edges, and nodes. This is useful in saving not only the storage but also the computing time.