International Journal of Computational Geometry & Applications

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.

We investigate the problem of computing a minimal-volume container for the non-overlapping packing of a given set of three-dimensional convex objects. Already the simplest versions of the problem are ${𝒩}{𝒫}$-hard so that we cannot expect to find polynomial time algorithms to determine the exact solution. We give constant ratio approximation algorithms for packing axis-parallel (rectangular) cuboids under translation into an axis-parallel (rectangular) cuboid as container, for packing cuboids under rigid motions into an axis-parallel cuboid or into an arbitrary convex container, and for packing convex polyhedra under rigid motions into an axis-parallel cuboid or arbitrary convex container. This work gives the first approximability results for the computation of minimum volume containers for the objects described.

Given a set $S$ of $n$ points in the plane, how many universal guards are sometimes necessary and always sufficient to guard any simple polygon with vertex set $S$? We call this problem a Universal Guard Problem and provide a spectrum of results. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of $n$ vertices, or to guard all polygons in a given set of $k$ polygons on an $n$-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.

We address the problem of reconstructing a polygon from the multiset of its edges. Given $n$ line segments in the plane, find a polygon with $n$ vertices whose edges are these segments, or report that none exists. It is easy to solve the problem in $O(nlogn)$ time if we seek an arbitrary polygon or a simple polygon. We show that the problem is NP-complete for weakly simple polygons, that is, a polygon whose vertices can be perturbed by at most $𝜀$, for any $𝜀>0$, to obtain a simple polygon. We give $O(n)$-time algorithms for reconstructing weakly simple polygons: when all segments are collinear or the segment endpoints are in general position. These results extend to the variant in which the segments are directed.

We study related problems for the case that the union of the $n$ input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that creates a weakly simple polygon. We give worst-case upper and lower bounds for both problems.

One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al.² introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments.

We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of $n$ moving entities in ${ℝ}^1$, specified by linear interpolation in a sequence of $\tau$ time stamps, we show that all maximal groups can be computed in $O({\tau }^2{n}^4)$ time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of $\alpha (n)$ in the running time, where $\alpha$ denotes the inverse Ackermann function. In higher dimensions, we can compute all maximal groups in $O({\tau }^2{n}^{5}logn)$ time (for any constant number of dimensions), regardless of whether the time stamps of entities are the same or not.

We also show that one $\tau$ factor can be traded for a much higher dependence on $n$ by giving a $O(\tau n^4{2}^n)$ algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on $n$ and linear dependence on $\tau$.