The visibility graph of a set S ⊆ ℝ² is the graph whose vertices are the points of S, with two points x,y connected by an edge if and only if they see each other in S, that is, if the segment xy is contained in S. The edge density of this graph is known as the Beer index of S. Previously, it has been shown that a simply connected set S ⊆ ℝ² of unit Lebesgue measure with Beer index β > 0 contains a convex subset of measure Ω(β); in particular, for visibility graphs of simply connected sets, a positive edge density β > 0 implies the existence of a clique containing an Ω(β)-fraction of all vertices. The simple-connectivity assumption cannot be omitted, as there are non-simply-connected sets with Beer index 1 and no convex subset of positive measure. Nevertheless, in this paper, we extend the above result to non-simply-connected sets, by showing that a visibility graph with large edge density contains a triangle with large convex hull. More precisely, we show that a set S ⊆ ℝ² of unit Lebesgue measure with Beer index β > 0 contains three pairwise visible points whose convex hull has measure Ω(β⁹). If in addition S is an open domain with K holes, then S contains three pairwise visible points with convex hull of measure Ω(β/K) as well as a convex subset of measure Ω(β/K²).

We study the heterogeneous facility location game model of n selfish agents on a line, where each agent’s reachable range is a closed subinterval of the line. From two possible facilities, f1 and f2, exactly one is chosen to be built on some point of the line, and the agents have their own preferences p1, p2∈[0,1], p1+p2=1, over these two facilities. The utility of the agent is pi if the placement of the chosen facility fi is inside her reachable range, and zero otherwise. The task is to design mechanisms which get the input from the agents and select the type and placement point of the facility to be built, such that it maximizes the social welfare (defined as the total utility of all agents) while ensuring truthfulness, i.e., incentivizing agents to report their preferences (both facility type and placement) honestly as a dominant strategy. We analyze various scenarios with different setting of privacy of agents’ positional and preference information. When the information is private to the agent, they have the option to misreport it, and hence, we will distinguish between reported information and public information. Initially, we consider the case where all facility preferences are 0 or 1 and we design an optimal mechanism for this case. We then study the case with fractional facility preferences. For the case of public preferences and reported positions, we obtain a mechanism yielding a 3-approximation of the optimum social welfare, and we prove that no deterministic mechanism can achieve approximation ratio better than 4/3. Next, we study the case with public positions and reported preferences. In this setting we design a randomized 2-approximation, obtain lower bounds 3 and 3/2 for the approximation factor of deterministic and randomized strategyproof mechanisms, respectively, and show that a dictator-based approach is a 16/7-approximation mechanism, where the 16/7 factor is tight. Finally, we extend our results to the case of m facilities.

Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.

A terrain is an $x$-monotone polygon whose lower boundary is a single line segment. We present an algorithm to find in a terrain a triangle of largest area in $O(nlog n)$ time, where $n$ is the number of vertices defining the terrain. The best previous algorithm for this problem has a running time of $O(n^2)$.