Given a set of disks in the plane, the goal of the problem studied in this paper is to choose a subset of these disks such that none of its members contains the centre of any other. Each disk not in this subset must be merged with one of its nearby disks that is, increasing the latter’s radius. This problem has applications in labelling rotating maps and in visualizing the distribution of entities in static maps. We prove that this problem is NP-hard. We also present an ILP formulation for this problem, and a polynomial-time algorithm for the special case in which the centres of all disks are on a line.

A polygonal curve is simplified to reduce its number of vertices, while maintaining similarity to its original shape. Numerous results have been published for vertex-restricted simplification, in which the vertices of the simplified curve are a subset of the vertices of the input curve. In curve-restricted simplification, i.e. when the vertices of the simplified curve are allowed to be placed on the edges of the input curve, the number of vertices may be much more reduced. In this paper, we present algorithms for computing curve-restricted simplifications of polygonal curves under the local Hausdorff distance measure.

We study the problem of finding hotspots, i.e. regions, in which a moving entity spends a significant amount of time, for polygonal trajectories. The fastest exact algorithm, due to Gudmundsson, van Kreveld, and Staals (2013) finds an axis-parallel square hotspot of fixed side length in O( n 2 ) for a trajectory with n edges. Limiting ourselves to the case in which the entity moves in a direction parallel either to the x or to the y-axis, we present an approximation algorithm with the time complexity O( n log 3 n) and approximation factor 1/2.

Given a multiset of colors as the query and a list-colored graph, i.e., an undirected graph with a set of colors assigned to each of its vertices, in the NP-hard list-colored graph motif problem the goal is to find the largest connected subgraph such that one can select a color from the set of colors assigned to each of its vertices to obtain a subset of the query. This problem was introduced to find functional motifs in biological networks. We present a branch-and-bound algorithm named RANGI for finding and enumerating list-colored graph motifs. As our experimental results show, RANGI's pruning methods and heuristics make it quite fast in practice compared to the algorithms presented in the literature. We also present a parallel version of RANGI that achieves acceptable scalability.