Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter
Publication date
2025-10-01
Authors
Picarella, Gianmarco
van Kreveld, Marc
Staals, Frank
de Vries, Sjoerd
Editors
Benoit, Anne
Kaplan, Haim
Wild, Sebastian
Wild, Sebastian
Herman, Grzegorz
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
Abstract
We study the problem of computing a convex region with bounded area and diameter that contains the maximum number of points from a given point set P. We show that this problem can be solved in O(n6k) time and O(n3k) space, where n is the size of P and k is the maximum number of points in the found region. We experimentally compare this new algorithm with an existing algorithm that does the same but without the diameter constraint, which runs in O(n3k) time. For the new algorithm, we use different diameters. We use both synthetic data and data from an application in cancer detection, which motivated our research.
Keywords
convex polygon, dynamic programming, implementation, Software
Citation
Picarella, G, van Kreveld, M, Staals, F & de Vries, S 2025, Computing Largest Subsets of Points Whose Convex Hulls Have Bounded Area and Diameter. in A Benoit, H Kaplan, S Wild, S Wild & G Herman (eds), 33rd Annual European Symposium on Algorithms, ESA 2025., 23, Leibniz International Proceedings in Informatics, LIPIcs, vol. 351, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, 15/09/25. https://doi.org/10.4230/LIPIcs.ESA.2025.23, conference