Conversion of a digital object into a finite set of balls: two complexity results – Isabelle Sivignon
- Date
- 25 May 2026, 14:15–15:00
- Location
- Theatrum Visuale, room 100155, building 10, Ångström Laboratory
- Type
- Seminar
- Lecturer
- Isabelle Sivignon
- Organiser
- Centre for Image Analysis
- Contact person
- Natasa Sladoje
We address the problem of converting a 2D digital object S (a finite set of points in Z^2) into a finite set B of balls centered on R^2, such that the balls of B cover all points of S and no point of Z^2\S, and the cardinality of B is minimum. We present two complexity results about this problem: first, we prove that the problem is NP-complete in the general case using a reduction from the 3-Planar Vertex Cover problem; then, we show that the problem becomes polynomial when restricted to the specific class of 2D hole-free digital objects.
Speaker: Isabelle Sivignon