Abstract
In this paper, we discuss approaches to constructing convex polyhedral enclosures of interval-based hierarchical structures. Hierarchical object representations are the data structures most frequently used for reconstructing real scenes. This object modelling does not depend on the nature of a real solid but only on the chosen maximum level of the hierarchical structure. This is a useful property for objects with complex shapes that are difficult to describe via exact mathematical formulas. We focus on reliable object modeling using an interval-based octree data structure. To obtain a convex polyhedral enclosure of an octree, we seek feasible ways to limit the number of considered points. For this purpose, we use the concept of extreme vertices of the tree nodes. Accurate algorithms for constructing the convex hull of these vertices yield a convex polyhedron as an adaptive and reliable object enclosure at each level of the tree.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The Quickhull algorithm for convex hull. ACM Transactions on Mathematical Software 22(4), 469–483 (1996)
Dyllong, E.: Akkurate Abstandsalgorithmen mit Ergebnisverifikation. Ph.D. thesis, University of Duisburg-Essen, VDI Reihe 20, Nr. 390, Düsseldorf (2004)
Dyllong, E., Luther, W.: Verified convex hull and distance computation for octree-encoded objects. Journal of Computational and Applied Mathematics (2006)
Fausten, D., Luther, W.: Verifizierte Lösungen von nichtlinearen polynomialen Gleichungssystemen. Technical Report SM-DU-477, University of Duisburg (2000)
Grimm, C.: Verläßliche Abstandsalgorithmen für intervallbasierte Octreemodelle und ihre konvexen Einschlüsse – Ein Effizienzvergleich. Diploma thesis, University of Duisburg (2006)
Hammer, R., Hocks, M., Kulisch, U., Ratz, D.: C++ Toolbox for Verified Computing. Basic Numerical Problems. Springer, Berlin (1995)
Krivsky, S., Lang, B.: Using Interval Arithmetic for Determining the Structure of Convex Hulls. Numerical Algorithms 37, 233–240 (2004)
Moore, R.: Interval Analysis. Prentice Hall, Englewood Cliffs (1966)
Ratschek, H., Rokne, J.: Geometric Computations with Interval and New Robust Methods. Horwood Publishing, Chichester (2003)
Samet, H.: The Design and Analysis of Spatial Data Structures. Addison-Wesley Publishing Company, Reading (1990)
Zhang, Min.: Konvexe Einschlüsse von hierarchischen intervallbasierten Modellen. Diploma thesis, University of Duisburg-Essen (2005)
Walach, E., Zeheb, E.: Sign Test of Multivariate Real Polynomials. IEEE Trans. on Circuits and Systems 27(7), 619–625 (1980)
Jaulin, J., Kieffer, M., Didrit, O., Walter, E.: Applied Interval Analysis. Springer, London (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dyllong, E. (2008). Convex Polyhedral Enclosures of Interval-Based Hierarchical Object Representations. In: Hertling, P., Hoffmann, C.M., Luther, W., Revol, N. (eds) Reliable Implementation of Real Number Algorithms: Theory and Practice. Lecture Notes in Computer Science, vol 5045. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85521-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-85521-7_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85520-0
Online ISBN: 978-3-540-85521-7
eBook Packages: Computer ScienceComputer Science (R0)