For researchers in the fields of cartography and graph drawing, the placement problem of text labels for the corresponding graphical objects is a challenging issue they may often encounter. This work focuses on studying the problem of placing rectangular text labels onto a set of fixed disks possibly with overlapping such that users may easily recognize the disks and labels, and the correspondence relationship between the disks and the corresponding labels by just visualising the layout of the disks and the labels. In this paper, we propose an innovative method based on force-directed mechanism to place labels at the appropriate locations with respect to the given positions of the disks. The method starts by placing the given labels at the centers of their corresponding disks respectively, and proceeds with pushing around the labels via applying specific attractive and repulsive forces between the disks and labels so that the overlapping situation between the labels are greatly improved or even completely eliminated, and the correspondence relationship between the disks and the corresponding labels become more easily recognizable. User survey results show that our method is effective in producing outputs with both good visibility rates of disks and labels and good correspondence rate between disks and the corresponding labels. The applications of such a label placement problem studied include labeling a set of circular regions appeared in the real world, such as labeling a set of signal coverage zones of the base stations in the cellular telephone network of some telecommunication company in an urban city.

In many applications, the logic of the program can be described using a task graph, where the data dependencies and execution time of each task are described. These dependencies create precedence constraints among tasks, which are requirements that some tasks must be finished before some other tasks. Many efforts have been put into scheduling parallelizable tasks that synchronically use multiple cores. In some cases, the task can be chunked into smaller pieces and scheduled independently, allowing further flexible schedules. However, it is usually either assumed that such splitting has no overhead, or that precedence constraints are not present, or that the user has to provide the way of splitting. This paper addresses the problem where these factors are considered together, that is scheduling splittable tasks with precedence constraints, where splitting introduces an overhead and the splitting of tasks are determined by the algorithm. The objective is to minimize the makespan of the schedule. We first present a mixed-integer quadratic program (MIQP) formulation of the problem. Then, a genetic algorithm (GA) is devised and its performance is compared with the MIQP solutions. We show that the genetic algorithm can produce reasonably good schedules compared with MIQP output within a significantly shorter time, and it has the potential to handle large task graphs.

Schematic metro maps provide an effective means of simplifying the geographical configuration of public rapid transportation systems. Nonetheless, travelers still find it difficult to identify routes of a specific topology on the maps because it is usually hidden behind the conventional octilinear layout of the entire map. In this paper, we present an approach to designing schematic maps with loop lines, which are drawn as circles together with annotation labels for guiding different traveling purposes. Our idea here is to formulate the aesthetic criteria as mathematical constraints in the mixed-integer programming model, which allows us to either align stations on the loop line at a grid if they are interchange stations or noninterchange stations on a circle otherwise. We then distribute the annotation labels associated with stations on the loop line evenly to the four side boundary of the map domain in order to make full use of the annotation space, while maximally avoiding intersections between leader lines and the metro network by employing a flow network algorithm. Finally, we present several experimental results generated by our prototype system to demonstrate the feasibility of the proposed approach.

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are: If the objects are 3-dimensional balls that roll on a plane, then we can detect collisions with a KDS of size O ( n log n ) that can handle events in O (log 2 n ) time. This structure processes O ( n 2 ) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. If the objects are convex fat 3-dimensional objects of constant complexity that are free-flying in ℝ 3 , then we can detect collisions with a KDS of O ( n log 6 n ) size that can handle events in O (log 7 n ) time. This structure processes O ( n 2 ) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. If the objects have similar sizes then the size of the KDS becomes O ( n ) and events can be handled in O (log n ) time.

Map labeling encounters unique issues in the context of dynamic maps with continuous zooming and panning-an application with increasing practical importance. In consistent dynamic map labeling, distracting behavior such as popping and jumping is avoided. In the model for consistent dynamic labeling that we use, a label becomes a 3d-solid, with scale as the third dimension. Each solid can be truncated to a single scale interval, called its active range, corresponding to the scales at which the label will be selected. The active range optimization (ARO) problem is to select active ranges so that no two truncated solids overlap and the sum of the heights of the active ranges is maximized. The simple ARO problem is a variant in which the active ranges are restricted so that a label is never deselected when zooming in. We investigate both the general and simple variants, for 1d- as well as 2d-maps. The 1d-problem can be seen as a scheduling problem with geometric constraints, and is also closely related to geometric maximum independent set problems. Different label shapes define different ARO variants. We show that 2d-ARO and general 1d-ARO are NP-complete, even for quite simple shapes. We solve simple 1d-ARO optimally with dynamic programming, and present a toolbox of algorithms that yield constant-factor approximations for a number of 1d- and 2d-variants.

We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases.We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.