A study on two geometric location problems
type: Item
instance of: scholarly article
title: A study on two geometric location problems
zbMATH Open document ID: 0675.68071
DOI: 10.1016/0020-0190(88)90174-3
author: S. H. Smith
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68U99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 68R99
zbMATH DE Number: 4106314
zbMATH Keywords: computational geometry
zbMATH Keywords: p-center
zbMATH Keywords: dynamic programming
zbMATH Keywords: NP-hard
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90174-3
OpenAlex ID: W1975512711
cites work: Q4198056
cites work: On the Complexity of Some Common Geometric Location Problems
cites work: Q3992847
cites work: Q4176809
description: scientific article; zbMATH DE number 4106314