Abstract We study a geometric facility location problem under imprecision. Given n unit segments on the real line, each with one of k colors, the goal is to place a point on each segment such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given segment of each color. We prove that if the input segments are pairwise disjoint, the problem can be solved in O ( n ) time, even for segments of arbitrary length. For overlapping segments, the problem becomes much more difficult. Nevertheless, we show that it can be solved in $$O(n \log ^2 n)$$ O ( n log 2 n ) time when $$k=2$$ k = 2 , by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon $P$ with $n$ vertices. We give a randomized near-linear-time $(1-\varepsilon)$-approximation algorithm for this problem: in $O(n( \log^2 n + (1/\varepsilon^3) \log n + 1/\varepsilon^4))$ time we find a convex polygon contained in $P$ that, with probability at least $2/3$, has area at least $(1-\varepsilon)$ times the area of an optimal solution. We also obtain similar results for the variant of computing a convex polygon inside $P$ with maximum perimeter. To achieve these results we provide new results in geometric probability. The first result is a bound relating the area of the largest convex body inside $P$ to the probability that two points chosen uniformly at random inside $P$ are mutually visible. The second result is a bound on the expected value of the difference between the perimeter of any planar convex body $K$ and the perimeter of the convex hull of a uniform random sample inside $K$.

Given a set S of points in the plane, the k-Gabriel graph of S is the geometric graph with vertex set S , where 𝑝 𝑖 , 𝑝 𝑗 ∈ 𝑆 are connected by an edge if and only if the closed disk having segment ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ 𝑝 𝑖 ⁢ 𝑝 𝑗 as diameter contains at most k points of 𝑆 ∖ { 𝑝 𝑖 , 𝑝 𝑗 } . We consider the following question: What is the minimum value of k such that the k -Gabriel graph of every point set S contains a Hamiltonian cycle? For this value, we give an upper bound of 10 and a lower bound of 2. The best previously known values were 15 and 1, respectively.

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon P with n vertices. We give a randomized near-linear-time (1 − ϵ)-approximation algorithm for this problem: in O((n/ϵ6) log2 n log(1/δ)) time we find a convex polygon contained in P that, with probability at least 1 − δ, has area at least (1 − ϵ) times the area of an optimal solution.

Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.

Given a large weighted graph G = (V, E) and a subset U of V , we define several graphs with vertex set U in which two vertices are adjacent if they satisfy some prescribed proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the defined graphs and provide algorithms for their computation.