Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431108 | Journal of Discrete Algorithms | 2009 | 10 Pages |
Abstract
We consider the problem of removing c points from a set S of n points so that the remaining point set is optimal in some sense. Definitions of optimality we consider include having minimum diameter, having minimum area (perimeter) bounding box, having minimum area (perimeter) convex hull. For constant values of c , all our algorithms run in O(nlogn)O(nlogn) time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rossen Atanassov, Prosenjit Bose, Mathieu Couture, Anil Maheshwari, Pat Morin, Michel Paquette, Michiel Smid, Stefanie Wuhrer,