In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set @math of @math (weighted) uncertain points in the plane and each uncertain point has @math possible locations each associated with a probability for the point appearing at that location. The goal is to find a point @math in the plane which minimizes the maximum expected rectilinear distance from @math to all uncertain points of @math , and @math is called a rectilinear center. We present an algorithm that solves the problem in @math time. Since the input size of the problem is @math , our algorithm is optimal.
The @math -center problems on deterministic points are classical problems and have been studied extensively. When all points are in the plane, the problems on most distance metrics are NP-hard @cite_15 . However, some special cases can be solved in polynomial time, e.g., the one-center problem @cite_7 , the two-center problem @cite_8 , the rectilinear three-center problem @cite_20 , the line-constrained @math -center problems (where all centers are restricted to be on a given line in the plane) @cite_3 @cite_4 @cite_17 .
@cite_4 @cite_7 @cite_8 @cite_3 @cite_15 @cite_20 @cite_17
2755780781 2258388518 2046812523 2158196818 2133962824 2087653366 113922551
Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows: Abstract This paper considers the planar Euclidean two-center problem: given a planar n-point set S, find two congruent circular disks of the smallest radius covering S. The main result is a deterministic algorithm with running time O(nlog2nlog2logn), improving the previous O(nlog9n) bound of Sharir and almost matching the randomized O(nlog2n) bound of Eppstein. If a point in the intersection of the two disks is given, then we can solve the problem in O(nlogn) time with high probability. In this paper we study several instances of the alignedk-center problem where the goal is, given a set of points S in the plane and a parameter k ⩾ 1, to find k disks with centers on a line l such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line l is given in advance; we can solve this problem in time O(n log2 n). In the case where only the direction of l is fixed, we give an O(n2log2 n)-time algorithm. When l is an arbitrary line, we give a randomized algorithm with expected running time O(n4log2 n). Then we present (1+e)-approximation algorithms for these three problems. When we denote T(k, e) = (k e2+(k e) log k) log(1 e), these algorithms run in O(n log k + T(k, e)) time, O(n log k + T(k, e) e) time, and O(n log k + T(k, e) e2) time, respectively. For k = O(n1 3 log n), we also give randomized algorithms with expected running times O(n + (k e2) log(1 e)), O(n+(k e3) log(1 e)), and O(n + (k e4) log(1 e)), respectively. Given n demand points in the plane, the p-center problem is to find p supply points (anywhere in the plane) so as to minimize the maximum distance from a demand point to its respective nearest supply point. The p-median problem is to minimize the sum of distances from demand points to their respective nearest supply points. We prove that the p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard. In fact, we prove that it is NP-hard even to approximate the p-center problems sufficiently closely. The reductions are from 3-satisfiability. Rectilinear k-centers of a finite point set P ⊂ R2 are the centers of at most k congruent axis-parallel squares of minimal size whose union covers P. This paper describes a linear time algorithm based on the prune-and-search paradigm to compute rectilinear 3-centers. The algorithm is elementary in the sense that it does not build on any sophisticated data structures or other algorithms, except for linear time median finding. An implementation is publically available as part of the Computational Geometry Algorithms Library (CGAL). The (weighted) (k )-median, (k )-means, and (k )-center problems in the plane are known to be NP-hard. In this paper, we study these problems with an additional constraint that requires the sought (k ) facilities to be on a given line. We present efficient algorithms for various distance metrics such as (L_1,L_2,L_ ). Assume all (n ) weighted points are given sorted by their projections on the given line. For (k )-median, our algorithms for (L_1 ) and (L_ ) metrics run in (O( nk,n k n n, n2^ O( k n ) n ) ) time and (O( nk n,n k n ^2 n, n2^ O( k n ) ^2 n ) ) time, respectively. For (k )-means, which is defined only on the (L_2 ) metric, we give an (O( nk,n k n , n2^ O( k n ) ) ) time algorithm. For (k )-center, our algorithms run in (O(n n) ) time for all three metrics, and in (O(n) ) time for the unweighted version under (L_1 ) and (L_ ) metrics.