Variational Analysis on the Signed Distance Functions | Journal of Optimization Theory and Applications Skip to main content

Advertisement

Springer Nature Link
Log in

Variational Analysis on the Signed Distance Functions

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

The signed distance function (or oriented distance function) of a set in a metric space determines the distance of a given point from the boundary of the set, with the sign determined by whether the point is in the set or in its complement. The knowledge of signed distance functions is a very valuable information in various fields of applied mathematics such as collision detection, binary classification, shape analysis, fuzzy numbers ranking and level set methods. One distinguished feature of the signed distance function is that it reflects the geometric structure of the set much better than the distance function does. We explore many interesting analytical properties of signed distance functions and use them to construct convex functions with not convex subdifferential domains. Several examples are presented to illustrate most of these fine properties.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces. Springer, New York (2003)

    Book  MATH  Google Scholar 

  2. Osher, S., Sethian, J.A.: Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79, 12–49 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  3. Reiner, T., Mückl, G., Dachsbacher, C.: Interactive modeling of implicit surfaces using a direct visualization approach with signed distance functions. Comput. Graph. 35, 596–603 (2011)

    Article  Google Scholar 

  4. Armitage, D.H., Kuran, Ü.: The convexity of a domain and the superharmonicity of the signed distance function. Proc. Am. Math. Soc. 93, 598–600 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  5. Iwata, S., Nakatsukasa, Y., Takeda, A.: Computing the signed distances between overlapping ellipsoids. SIAM J. Optim. 25, 2359–2384 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  6. Delfour, M.C., Zolésio, J.P.: Shape analysis via oriented distance functions. J. Funct. Anal. 123, 129–201 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  7. Delfour, M.C., Zolésio, J.P.: Oriented distance function and its evolution equation for initial sets with thin boundary. SIAM J. Control Optim. 42, 2286–2304 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  8. Delfour, M.C., Zolésio, J.P.: Oriented Distance Functions in Shape Analysis and Optimization, Control and Optimal Design of Distributed Parameter Systems, pp. 39–72. Springer, New York (1995)

    MATH  Google Scholar 

  9. Delfour, M.C., Zolésio, J.P.: Shapes and Geometries. Metrics, Analysis, Differential Calculus, and Optimization, 2nd edn. SIAM, Philadelphia (2001)

    MATH  Google Scholar 

  10. Liu, C.G., Ng, K.F., Yang, W.H.: Merit functions in vector optimization. Math. Program. Ser. A. 119, 215–237 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chen, J., Ansari, Q., Yao, J.C.: Characterizations of set order relations and constrained set optimization problems via oriented distance function. Optimization 66, 1741–1754 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  12. Zaffaroni, A.: Degrees of efficiency and degrees of minimality. SIAM J. Control Optim. 42, 1071–1086 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  13. Fuhrmann, A., Sobottka, G., Gross, C.: Abstract distance fields for rapid collision detection in physically based modeling. In: Proceedings of international conference graphicon (2003)

  14. Boczko, E., DiLullo, A., Young, T.: Signed distance functions: a new tool in binary classification. arXiv:CS.LG/0511105 (2005)

  15. Abbasbandy, S., Asady, B.: Ranking of fuzzy numbers by sign distance. Inf. Sci. 176, 2405–2416 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  16. Sethian, J.A.: Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, Cambridge (1999)

    MATH  Google Scholar 

  17. Altangerel, L., Wanka, G., Wilfer, O.: An oriented distance function application to gap functions for vector variational inequalities. In: Optimization, simulation, and control, vol. 76. Springer, New York, pp. 17–34 (2013)

  18. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    Book  MATH  Google Scholar 

  19. Rockafellar, R.T., Wets, J.B.: Variational Analysis. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  20. Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I. Springer, New York (2006)

    Google Scholar 

  21. Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990)

    Book  MATH  Google Scholar 

  22. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011)

    Book  MATH  Google Scholar 

  23. Hiriart-Urruty, J.B.: New concepts in nondifferentiable programming. Bull. Soc. Math. France 60, 57–85 (1979)

    MathSciNet  MATH  Google Scholar 

  24. Hiriart-Urruty, J.B.: Tangent cones, generalized gradients and mathematical programming in Banach spaces. Math. Oper. Res. 4, 79–97 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  25. Bot, R.I., Kassay, G., Wanka, G.: Duality for almost convex optimization problems via the perturbation approach. J. Glob. Optim. 42, 385–399 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  26. Moffat, S.M., Moursi, W.M., Wang, X.: Nearly convex sets: fine properties and domains or ranges of subdifferentials of convex functions. Math. Program. Ser. A. 160, 193–223 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Hiriart-Urruty, J.B., Lemaréchal, C.: Fundamentals of Convex Analysis. Springer, Berlin (2001)

    Book  MATH  Google Scholar 

  28. Brezis, H., Haraux, A.: Image d’une somme d’operateurs monotones et applications. Israel J. Math. 23, 165–186 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  29. Simons, S.: From Hahn-Banach to Monotonicity. Springer, New York (2008)

    MATH  Google Scholar 

  30. Borwein, J.M., Giles, J.R.: The proximal normal formula in Banach space. Trans. Am. Math. Soc. 302, 371–381 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  31. Preiss, D., Zajćek, L.: Fréchet differentiation of convex functions in a Banach space with a separable dual. Proc. Am. Math. Soc. 91, 202–204 (1994)

    Google Scholar 

  32. Mangasarian, O.L.: Polyhedral boundary projection. SIAM J. Optim. 9, 1128–1134 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  33. Boyd, S., Vandenberghe, L.: Convex Optimization, Solutions Manual. Cambridge University Press, Cambridge (2006)

    Google Scholar 

  34. Hager, W.W., Zhang, H.C.: Projector onto a polyhedron that exploits sparsity. SIAM J. Optim. 29, 1773–1798 (2016)

    Article  MATH  Google Scholar 

  35. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

    Book  MATH  Google Scholar 

  36. Bauschke, H.H., Moffat, S.M., Wang, X.: Near equality, near convexity, sums of maximally monotone operators, and averages of firmly nonexpansive mappings. Math. Program. Ser. B. 139, 55–70 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  37. Zalinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002)

    Book  MATH  Google Scholar 

Download references

Acknowledgements

We are very grateful to two anonymous referees and Associate Editor C. Zalinescu whose insightful comments helped to considerably improve an earlier version of this paper. Honglin Luo was supported by NSFC (Nos. 11601050, 11431004) and CQNSF (Nos. KJ1600316, cstc2016jcyjA0116). Xianfu Wang was partially supported by the Natural Sciences and Engineering Research Council of Canada.

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Chongqing Normal University, Chongqing, 401331, China

    Honglin Luo

  2. Department of Mathematics, University of British Columbia, Kelowna, BC, Canada

    Xianfu Wang & Brett Lukens

  3. School of Mathematics and Statistics, Southwest University, Chongqing, People’s Republic of China

    Xianfu Wang

Authors
  1. Honglin Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xianfu Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Brett Lukens
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xianfu Wang.

Additional information

Communicated by Constantin Zalinescu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Luo, H., Wang, X. & Lukens, B. Variational Analysis on the Signed Distance Functions. J Optim Theory Appl 180, 751–774 (2019). https://doi.org/10.1007/s10957-018-1414-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-018-1414-2

Keywords

Mathematics Subject Classification

Search

Navigation