×

Computing \(D\)-convex hulls in the plane. (English) Zbl 1159.65022

The authors present an algorithm for computing the so called \(D\)-convex hull of a finite point set in the plane. A function is called \(D\)-convex if its restriction to each line parallel to a nonzero vector from a set of \(d\) vectors (directions) is convex. Unlike the separately convex hull where the set of direction vectors consists of linearly independent vectors (the standard basis in the \(d\)-dimensional space, for example), here a finite set of arbitrary nonzero direction vectors in the plane is considered.
The principle of the suggested algorithm is described on a concrete planar example and explained by many pictures. The results can be used in the areas where the particular case of \(D\)-convexity, so called rank-one convexity, appears – i.e. in calculus of variations, theory of partial differential equations, mathematical models of crystalline microstructure, etc.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
52A10 Convex sets in \(2\) dimensions (including convex curves)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aumann, R.; Hart, S., Bi-convexity and bi-martingales, Israel. J. Math., 54, 2, 159-180 (1986) · Zbl 0607.52001
[2] Cgal, Computational Geometry Algorithms Library · Zbl 1322.68279
[3] Casadio-Tarabusi, E., An algebraic characterization of quasiconvex functions, Ricerche Mat., 42, 11-24 (1993) · Zbl 0883.26011
[4] Dolzmann, G., Variational Methods for Crystalline Microstructure. Analysis and Computation, Lecture Notes in Mathematics, vol. 1803 (2003), Springer: Springer Berlin · Zbl 1016.74002
[5] Fink, E.; Wood, D., Fundamentals of restricted-orientation convexity, Inform. Sci., 92, 175-196 (1996) · Zbl 0885.52002
[6] Fink, E.; Wood, D., Generalized halfspaces in restricted-orientation convexity, J. Geom., 62, 99-120 (1998) · Zbl 0923.52001
[7] Kirchheim, B.; Müller, S.; Šverák, V., Studying nonlinear PDE by geometry in matrix space, (Hildebrandt, S.; etal., Geometric Analysis and Nonlinear Partial Differential Equations (2003), Springer: Springer Berlin), 347-395 · Zbl 1290.35097
[8] Matoušek, J., On directional convexity, Discrete Comput. Geom., 25, 3, 389-405 (2001) · Zbl 0989.52007
[9] Matoušek, J.; Plecháč, P., On functional separately convex hulls, Discrete Comput. Geom., 19, 105-130 (1998) · Zbl 0892.68102
[10] Matoušková, E.; Reich, S., The Hundal example revisited, J. Nonlin. Convex Anal., 4, 3, 411-428 (2003) · Zbl 1065.47048
[11] Müller, S., Variational models for microstructure and phase transitions, (Hildebrandt, S.; etal., Calculus of Variations and Geometric Evolution Problems. Calculus of Variations and Geometric Evolution Problems, Lecture Notes in Mathematics, vol. 1713 (1999), Springer: Springer Berlin), 85-210 · Zbl 0968.74050
[12] Nesi, V.; Milton, G. W., Polycrystalline configurations that maximize electrical resistivity, J. Mech. Phys. Solids, 39, 525-542 (1991) · Zbl 0734.73068
[13] V. Scheffer, Regularity and irregularity of solutions to nonlinear second order elliptic systems of partial differential equations and inequalities, Dissertation, Princeton University, 1974; V. Scheffer, Regularity and irregularity of solutions to nonlinear second order elliptic systems of partial differential equations and inequalities, Dissertation, Princeton University, 1974
[14] M. Seel, Implementation of planar Nef polyhedra, Research Report MPI-I-2001-1-003-1, Max-Planck-Institut für Informatik, Saarbrücken, 2001; M. Seel, Implementation of planar Nef polyhedra, Research Report MPI-I-2001-1-003-1, Max-Planck-Institut für Informatik, Saarbrücken, 2001
[15] Calc. Var. Partial Differ. Equ., 28, 4, 545-546 (2007), Erratum: · Zbl 1108.49011
[16] Székelyhidi, L., On the local structure of rank-one convex hulls, Proc. Am. Math. Soc., 134, 7, 1963-1972 (2006) · Zbl 1104.49014
[17] Tartar, L., On separately convex functions, (Kinderlehrer, D.; etal., Microstructure and Phase Transition. Microstructure and Phase Transition, The IMA Volumes in Mathematics and its Applications, vol. 54 (1993), Springer: Springer Berlin), 191-204 · Zbl 0823.26008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.