A new variational approach based on level-set function for convex hull problem with outliers

Lingfeng Li, Shousheng Luo*, Xue Cheng Tai, Jiang Yang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

6 Citations (Scopus)


Seeking the convex hull of an object (or point set) is a very fundamental problem arising from various tasks. In this work, we propose a variational approach based on the level-set representation for convex hulls of 2-dimensional objects. This method can adapt to exact and inexact convex hull problems. In addition, this method can compute multiple convex hulls simultaneously. In this model, the convex hull is characterized by the zero sublevel-set of a level-set function. For the exact case, we require the zero sublevel-set to be convex and contain the whole given object, where the convexity is characterized by the non-negativity of Laplacian of the level-set function. Then, the convex hull can be obtained by minimizing the area of the zero sublevel-set. For the inexact case, instead of requiring all the given points are included, we penalize the distance from all given points to the zero sublevel-set. Especially, the inexact model can handle the convex hull problem of the given set with outliers very well, while most of the existing methods fail. An efficient numerical scheme using the alternating direction method of multipliers is developed. Numerical examples are given to demonstrate the advantages of the proposed methods.

Original languageEnglish
Pages (from-to)315-338
Number of pages24
JournalInverse Problems and Imaging
Issue number2
Publication statusPublished - Apr 2021

Scopus Subject Areas

  • Analysis
  • Modelling and Simulation
  • Discrete Mathematics and Combinatorics
  • Control and Optimization

User-Defined Keywords

  • ADMM
  • Convex hull
  • Level-set method
  • Outliers
  • Variational method


Dive into the research topics of 'A new variational approach based on level-set function for convex hull problem with outliers'. Together they form a unique fingerprint.

Cite this