A study on two geometric location problems (Q1122367)

For a set S of points, two geometric location problems are considered in this paper: (A) For a positive real d, find a largest subset of S in which the distance between any two points is greater than d. (B) For a positive integer p, find a p-point subset of S in which the two closest points are farthest away. Both problems are considered in one- or two- dimensional Euclidean space, referred to as (A1), (A2), (B1), (B2). (A1) can be solved using sorting in O(n log n) time. A dynamic programming algorithm is given for solving (B1) in \(O(pn+n \log n)\) time. (A1) and (B1) have lower bounds \(\Omega\) (n log n). It is stated that problems (A2) and (B2) are polynomially equivalent, and the Maximum Independent Set for Circle Intersection Graphs (MISCIG) problem is polynomially reducible to problem (A2). It is proved that MISCIG is NP-complete. Thus, (A2) and (B2) are NP-hard.