Narrow Results

We consider the problem of augmenting an $n$-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in $O(n{log}^{3}n)$ time, and (ii) the input graph is a tree, running in $O(n^{2}logn)$ time. We also present an algorithm for paths that computes a $(1+𝜀)$-approximation in $O(n+1/{𝜀}^3)$ time.

We present efficient algorithms for two problems of facility location. In both problems we want to determine the location of a single facility with respect to n given sites. In the first we seek a location that maximizes a weighted distance function between the facility and the sites, and in the second we find a location that minimizes the sum (or sum of the squares) of the distances of k of the sites from the facility.

We deal with a map-abeling problem, named LOFL (Left-part Ordered Flexible Labeling), to label a set of points in a plane in the presence of polygonal obstacles. The label for each point is selected from a set of rectangles with various shapes satisfying the left-part ordered property, and is placed near to the point after scaled by a scaling factor σ which is common to all points. In this paper, we give an optimal O((n + m) log (n + m)) algorithm to decide the feasibility of LOFL for a fixed scaling factor σ, and an O((n + m) log² (n + m)) time algorithm to find the largest feasible scaling factor σ, where n is the number of points and m is the total number of edges of the polygonal obstacles.

In this paper, we study several interesting optimal-ratio region detection (ORD) problems in d-D (d ≥ 3) discrete geometric spaces, which arise in high dimensional medical image segmentation. Given a d-D voxel grid of n cells, two classes of geometric regions that are enclosed by a single or two coupled smooth heighfield surfaces defined on the entire grid domain are considered. The objective functions are normalized by a function of the desired regions, which avoids a bias to produce an overly large or small region resulting from data noise. The normalization functions that we employ are used in real medical image segmentation. To our best knowledge, no previous results on these problems in high dimensions are known. We develop a unified algorithmic framework based on a careful characterization of the intrinsic geometric structures and a nontrivial graph transformation scheme, yielding efficient polynomial time algorithms for solving these ORD problems. Our main ideas include the following. We observe that the optimal solution to the ORD problems can be obtained via the construction of a convex hull for a set of O(n) unknown 2-D points using the hand probing technique. The probing oracles are implemented by computing a minimum s-t cut in a weighted directed graph. The ORD problems are then solved by O(n) calls to the minimum s-t cut algorithm. For the class of regions bounded by a single heighfield surface, our further investigation shows that the O(n) calls to the minimum s-t cut algorithm are on a monotone parametric flow network, which enables to detect the optimal-ratio region in the complexity of computing a single maximum flow.

Given a set S of weighted points in the plane, we consider two problems dealing with lines in ℝ² under the weighted Euclidean distance: (1) Preprocess S into a data structure that efficiently finds a nearest point among S to a query line. (2) Find an optimal line that maximizes the minimum of the weighted distance to any point of S. The latter problem is also known as the obnoxious line location problem. We introduce a unified approach to both problems based on a new geometric transformation that maps lines in the plane to points in a line space. It turns out that our transformation, together with its target space, well describes the proximity relations between given weighted points S and every line in ℝ². We define a Voronoi-like tessellation on the line space and investigate its geometric, combinatorial, and computational properties. As its direct applications, we obtain several new algorithmic results on the two problems. We also show that our approach extends to weighted line segments and weighted polygons.

In 1982, Drezner proposed the $(1|1)$-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and the follower opens the second. Customers will each patronize the facility closer to them (with ties broken in favor of the first one), thereby deciding the market share of the two facilities. The goal is to find the best position for the leader’s facility so that its market share is maximized. The best algorithm of this problem is an $O(n^{2}logn)$-time parametric search approach, which searches over the space of market share values.

In the same paper, Drezner also proposed a generalized version of $(1|1)$-centroid problem by introducing a minimal distance constraint $R$, such that the follower’s facility is not allowed to be located within a distance $R$ from the leader’s. He proposed an $O(n^{5}logn)$-time algorithm for this generalized version by identifying $O(n^4)$ points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the $O(n^4)$ candidate points, and present an $O(n^{2}logn)$-time algorithm for this generalized version, thereby closing the $O(n^3)$ gap between the two bounds.

In this paper we consider the following $2$-Central Path Problem (2CPP): Given a set of $m$ polygonal curves ${𝒫}=\{P_1,P_2,\dots ,P_m\}$ in the plane, find two curves $P_u$ and $P_l$, called $2$-central paths, that best represent all curves in ${𝒫}$. Despite its theoretical interest and a wide range of practical applications, 2CPP has not been well studied. In this paper, we first establish criteria that $P_u$ and $P_l$ ought to meet in order for them to best represent ${𝒫}$. In particular, we require that there exists parametrizations $f_u(t)$ and $f_l(t)$ ($t\in [a,b]$) of $P_u$ and $P_l$ respectively such that the maximum distance from $\{f_u(t),f_l(t)\}$ to curves in ${𝒫}$ is minimized. Then an efficient algorithm is presented to solve 2CPP under certain realistic assumptions. Our algorithm constructs $P_u$ and $P_l$ in $O(nm{log}^{4}n{2}^{\alpha (n)}\alpha (n))$ time, where $n$ is the total complexity of ${𝒫}$ (i.e., the total number of vertices and edges), $m$ is the number of curves in ${𝒫}$, and $\alpha (n)$ is the inverse Ackermann function. Our algorithm uses parametric search technique and is considerably faster than arrangement-related algorithms (i.e. $\mathrm{\Omega }(n^2)$) when $m\ll n$ as in most real applications.

In this paper, we study the enumerative versions of the interdistance in terdis stance ranking and selection problems in space, namely, the fixed-radius near neighbors and interdistance enumeration problems, respectively. The input to the fixed-radius near neighbors problem is a set of n points S⊆ℜ^d and a nonnegative real number δ, and the output consists of all pairs of points within interdistance δ. We give an algorithm which, after an O(n log n) time preprocessing step, answers a fixed-radius near neighbors query with respect to an L_p metric in O(n+ρ(δ)) time, where ρ(δ) is the rank of δ. The space needed is O(n). The input to the interdistance enumeration problem is a set of n points S⃄ℜ^d and an integer k, , and the output is a set of point pairs, each corresponding to an interdistance having length less than or equal to the interdistance with rank k. We offer an O(n log n+k) time, O(n+k) space algorithm for this problem. This algorithm also works for any L_p metric.

Let S be a set of n points in ℝ^d, and let each point p of S have a positive weight w(p). We consider the problem of computing a ray R emanating from the origin (resp. a line l through the origin) such that min_{p ∈ s} w(p) · d(p,R) (resp. min_{p ∈ S} w(p) · d(p,l)) is maximal. If all weights are one, this corresponds to computing a silo emanating from the origin (resp. a cylinder whose axis contains the origin) that does not contain any point of S and whose radius is maximal. For d = 2, we show how to solve these problems in O(n log n) time, which is optimal in the algebraic computation tree model. For d = 3, we give algorithms that are based on the parametric search technique and run in O(n log⁴ n) time. The previous best known algorithms for these three-dimensional problems had almost quadratic running time. In the final part of the paper, we consider some related problems.