A study on two geometric location problems
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.
- Geometric complexity of some location problems
- Integer-friendly formulations for the \(r\)-separation problem
- Hierarchically specified unit disk graphs
- A geometrical solution for quadratic bicriteria location models
- On the complexity of two circle connecting problems
- A comparison of \(p\)-dispersion heuristics
- Maximum independent set and maximum clique algorithms for overlap graphs
- Dispersing points on intervals
- Dispersing and grouping points on planar segments
- On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon
- Facility location with tree topology and radial distance constraints
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Faster approximation for maximum independent set on unit disk graph
- Maximizing single attribute diversity in group selection
- Parameterized study of Steiner tree on unit disk graphs
- Minimizing co-location potential of moving entities
- Representation of the non-dominated set in biobjective discrete optimization
- Computing Maximally Separated Sets in the Plane
- Testing consumer rationality using perfect graphs and oriented discs
- scientific article; zbMATH DE number 1974112 (Why is no real title available?)
- scientific article; zbMATH DE number 754942 (Why is no real title available?)
- scientific article; zbMATH DE number 4003525 (Why is no real title available?)
- Diversity maximization in doubling metrics
- A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
- scientific article; zbMATH DE number 7650083 (Why is no real title available?)
- Max-min dispersion on a line
- Away from each other
- Obtaining approximately optimal and diverse solutions via dispersion
- Algorithms for \(k\)-dispersion for points in convex position in the plane
- Hierarchically specified unit disk graphs
- Theory and application of width bounded geometric separators
- Dispersion problem on a convex polygon
- Finding diverse strings and longest common subsequences in a graph
- Algorithms for minimizing the movements of spreading points in linear domains
- Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
- Algorithms for k-dispersion for points in convex position in the plane
- Dynamic parameterized problems on unit disk graphs
- Dominating set, independent set, discrete k-center, dispersion, and related problems for planar points in convex position
- A couple of simple algorithms for k-dispersion
- Max-min four-dispersion problems
This page was built for publication: A study on two geometric location problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122367)
