Search

We consider a random variable expressed as the Euclidean distance between an arbitrary point and a random variable uniformly distributed in a closed and bounded set of a three-dimensional Euclidean space. Four cases are considered for this set: a union of disjoint disks, a union of disjoint balls, a union of disjoint line segments, and the boundary of a polyhedron. In the first three cases, we provide closed-form expressions of the cumulative distribution function and the density. In the last case, we propose two algorithms with complexity O (n ln n) , n being the number of edges of the polyhedron, that computes exactly the cumulative distribution function. An application of these results to probabilistic seismic hazard analysis and extensions are discussed. Finally, we present an open source library, available at https://github.com/vguigues/Areas%5fLibrary , that implements the algorithms presented in this paper. [ABSTRACT FROM AUTHOR]

In the present paper, we propose a novel generalization of the celebrated MMP algorithm in order to find the wavefront propagation and the cut-locus on a convex polyhedron with an emphasis on actual implementation for instantaneous visualization and numerical computation. [ABSTRACT FROM AUTHOR]

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(n2logn)-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(n5logn)-time algorithm for this generalized version by identifying O(n4) 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(n4) candidate points, and present an O(n2logn)-time algorithm for this generalized version, thereby closing the O(n3) gap between the two bounds. [ABSTRACT FROM AUTHOR]

In this paper, we consider an interval coverage problem. We are given intervals of the same length on a line and a line segment on . Each interval has a nonnegative weight. The goal is to move the intervals along such that every point of is covered by at least one interval and the maximum moving cost of all intervals is minimized, where the moving cost of each interval is its moving distance times its weight. Algorithms for the 'unweighted' version of this problem have been given before. In this paper, we present a first-known algorithm for this weighted version and our algorithm runs in time. The problem has applications in mobile sensor barrier coverage, where is the barrier and each interval is the covering interval of a mobile sensor. [ABSTRACT FROM AUTHOR]

In this paper, we consider the distributed version of Support Vector Machine (SVM) under the coordinator model, where all input data (i.e., points in ℝ d space) of SVM are arbitrarily distributed among k nodes in some network with a coordinator which can communicate with all nodes. We investigate two variants of this problem, with and without outliers. For distributed SVM without outliers, we prove a lower bound on the communication complexity and give a distributed (1 −) -approximation algorithm to reach this lower bound, where is a user specified small constant. For distributed SVM with outliers, we present a (1 −) -approximation algorithm to explicitly remove the influence of outliers. Our algorithm is based on a deterministic distributed top t selection algorithm with communication complexity of O (k log (t)) in the coordinator model. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of designing robust algorithms for computing the minimum spanning tree, the nearest neighbor graph, and the relative neighborhood graph of a set of points in the plane, under the Euclidean metric. We use the term "robust" to denote an algorithm that can properly handle degenerate configurations of the input (such as co-circularities and collinearities) and that is not affected by errors in the flow of control due to round-off approximations. Existing asymptotically optimal algorithms that compute such graphs are either suboptimal in terms of the arithmetic precision required for the implementation, or cannot handle degeneracies, or are based on complex data structures. We present a unified approach to the robust computation of the above graphs. The approach is a variant of the general region approach for the computation of proximity graphs based on Yao graphs, first introduced in Ref. 43 (A. C.-C. Yao, On constructing minimum spanning trees in k -dimensional spaces and related problems, SIAM J. Comput.11(4) (1982) 721–736). We show that a sparse supergraph of these geometric graphs can be computed in asymptotically optimal time and space, and requiring only double precision arithmetic, which is proved to be optimal. The arithmetic complexity of the approach is measured by using the notion of degree, introduced in Ref. 31 (G. Liotta, F. P. Preparata and R. Tamassia, Robust proximity queries: An illustration of degree-driven algorithm design, SIAM J. Comput.28(3) (1998) 864–889) and Ref. 3 (J. D. Boissonnat and F. P. Preparata, Robust plane sweep for intersecting segments, SIAM J. Comput.29(5) (2000) 1401–1421). As a side effect of our results, we solve a question left open by Katajainen27 (J. Katajainen, The region approach for computing relative neighborhood graphs in the L p metric, Computing40 (1987) 147–161) about the existence of a subquadratic algorithm, based on the region approach, that computes the relative neighborhood graph of a set of points S in the plane under the L 2 metric. [ABSTRACT FROM AUTHOR]

In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set 𝒫 of n (weighted) uncertain points in the plane and each uncertain point has m possible locations each associated with a probability for the point appearing at that location. The goal is to find a point q ∗ in the plane which minimizes the maximum expected rectilinear distance from q ∗ to all uncertain points of 𝒫 , and q ∗ is called a rectilinear center. We present an algorithm that solves the problem in O (m n) time. Since the input size of the problem is Θ (m n) , our algorithm is optimal. [ABSTRACT FROM AUTHOR]

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.2 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 τ time stamps, we show that all maximal groups can be computed in O(τ2n4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of α(n) in the running time, where α denotes the inverse Ackermann function. In higher dimensions, we can compute all maximal groups in O(τ2n5logn) 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 τ factor can be traded for a much higher dependence on n by giving a O(τn42n) 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 nand linear dependence on τ. [ABSTRACT FROM AUTHOR]

An unfolding of a polyhedron is a single connected planar piece without overlap resulting from cutting and flattening the surface of the polyhedron. Even for orthogonal polyhedra, it is known that edge-unfolding, i.e., cuts are performed only along the edges of a polyhedron, is not sufficient to guarantee a successful unfolding in general. However, if additional cuts parallel to polyhedron edges are allowed, it has been shown that every orthogonal polyhedron of genus zero admits a grid-unfolding with quadratic refinement. Using a new unfolding technique developed in this paper, we improve upon the previous result by showing that linear refinement suffices. For 1-layer orthogonal polyhedra of genus , we show a grid-unfolding algorithm using only additional cuts, affirmatively answering an open problem raised in a recent literature. Our approach not only requires fewer cuts but yields much simpler algorithms. [ABSTRACT FROM AUTHOR]

The Fréchet distance is a well studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown to be optimal assuming the Strong Exponential Time Hypothesis (SETH) [Bringmann, FOCS'14]. To overcome the worst-case quadratic time barrier, restricted classes of curves have been studied that attempt to capture realistic input curves. The most popular such class are -packed curves, for which the Fréchet distance has a -approximation in time [Driemel et al., DCG'12]. In dimension this cannot be improved to for any unless SETH fails [Bringmann, FOCS'14]. In this paper, exploiting properties that prevent stronger lower bounds, we present an improved algorithm with time complexity . This improves upon the algorithm by Driemel et al. for any . Moreover, our algorithm's dependence on , and is optimal in high dimensions apart from lower order factors, unless SETH fails. Our main new ingredients are as follows: For filling the classical free-space diagram we project short subcurves onto a line, which yields one-dimensional separated curves with roughly the same pairwise distances between vertices. Then we tackle this special case in near-linear time by carefully extending a greedy algorithm for the Fréchet distance of one-dimensional separated curves. [ABSTRACT FROM AUTHOR]

A variation on the classical polygon illumination problem was introduced in [Aichholzer et al. EuroCG'09]. In this variant light sources are replaced by wireless devices called -modems, which can penetrate a fixed number , of 'walls'. A point in the interior of a polygon is 'illuminated' by a -modem if the line segment joining them intersects at most edges of the polygon. It is easy to construct polygons of vertices where the number of -modems required to illuminate all interior points is . However, no non-trivial upper bound is known. In this paper we prove that the number of kmodems required to illuminate any polygon of vertices is . For the cases of illuminating an orthogonal polygon or a set of disjoint orthogonal segments, we give a tighter bound of . Moreover, we present an time algorithm to achieve this bound. [ABSTRACT FROM AUTHOR]

Necklace maps visualize quantitative data associated with regions by placing scaled symbols, usually disks, without overlap on a closed curve (the necklace) surrounding the map regions. Each region is projected onto an interval on the necklace that contains its symbol. In this paper we address the algorithmic question how to maximize symbol sizes while keeping symbols disjoint and inside their intervals. For that we reduce the problem to a one-dimensional problem which we solve efficiently. Solutions to the one-dimensional problem provide a very good approximation for the original necklace map problem. We consider two variants: Fixed-Order, where an order for the symbols on the necklace is given, and Any-Order where any symbol order is possible. The Fixed-Order problem can be solved in O(n log n) time. We show that the Any-Order problem is NP-hard for certain types of intervals and give an exact algorithm for the decision version. This algorithm is fixed-parameter tractable in the thickness K of the input. Our algorithm runs in O(n log n + n2K4K) time which can be improved to O(n log n + nK2K) time using a heuristic. We implemented our algorithm and evaluated it experimentally. [ABSTRACT FROM AUTHOR]