2021/08/17 by Therese Biedl, Biedl, Therese, Anna Lubiw +7
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.2108.07751
Full-length version of a paper to appear at ESA'21
arxiv created 2021/08/17 · arxiv updated 2021/08/18
The input to the distant representatives problem is a set of n objects in the plane and the goal is to find a representative point from each object while maximizing the distance between the closest pair of points. When the objects are axis-aligned rectangles, we give polynomial time constant-factor approximation algorithms for the L1, L2, and L_∞ distance measures. We also prove lower bounds on the approximation factors that can be achieved in polynomial time (unless P = NP).