Search

Given a pair of start and target configurations, each consisting of n pairwise disjoint disks in the plane, what is the minimum number of moves that suffice for transforming the start configuration into the target configuration? In one move a disk is lifted from the plane and placed back in the plane at another location, without intersecting any other disk. We discuss efficient algorithms for this task and estimate their number of moves under different assumptions on disk radii. We then extend our results for arbitrary disks to systems of pseudodisks, in particular to sets of homothetic copies of a convex object.

In this paper we investigate the problem of locating a mobile facility at (or near) the center of a set of clients that move independently, continuously, and with bounded velocity. It is shown that the Euclidean 1-center of the clients may move with arbitrarily high velocity relative to the maximum client velocity. This motivates the search for strategies for moving a facility so as to closely approximate the Euclidean 1-center while guaranteeing low (relative) velocity.In this paper we investigate the problem of locating a mobile facility at (or near) the center of a set of clients that move independently, continuously, and with bounded velocity. It is shown that the Euclidean 1-center of the clients may move with arbitrarily high velocity relative to the maximum client velocity. This motivates the search for strategies for moving a facility so as to closely approximate the Euclidean 1-center while guaranteeing low (relative) velocity.

We study the problem of computing an equitable 2-fan for three masses distributed on the 2-sphere. The existence of an equitable 2-fan was shown by Barany and Matousek. The contribution of this paper is twofold. (i) We prove the existence of an infinite set of equitable 2-fans. (ii) We present an efficient algorithm for finding an equitable 2-fan when the mass distributions are discrete, i.e. finite sets of points. Both (i) and (ii) can be easily extended to mass distributions in the plane instead of the sphere.

Abstract: Drugs and other chemical compounds are often modeled as polygonal shapes, where each vertex represents an atom of the molecule, and covalent bonds between atoms are represented by edges between the corresponding vertices. This polygonal shape derived from a chemical compound is often called its molecular graph, and can be a path, a tree, or in general a graph. An indicator defined over this molecular graph, the Wiener index, has been shown to be strongly correlated to various chemical properties of the compound. The Wiener index conjecture for trees states that for any integer n (except for a finite set), one can find a tree with Wiener index n. This conjecture has been open for quite some time, and many authors have presented incremental progress on this problem. In this paper we present further progress towards proving this conjecture—through the design of efficient algorithms, we show that enumerating all possible trees to verify this conjecture (as done by all the previous approaches) is not necessary, but instead searching in a small special family of trees suffices, thus achieving the first polynomial (in n) time algorithm to verify the conjecture up to integer n. More precisely, we (i) present an infinite family of trees and prove various properties of these trees, (ii) show that a large number of integers, up to at least 108 (compared with the previous best 104) are representable as Wiener indices of trees in this succinct family, (iii) provide several efficient algorithms for computing trees with given Wiener indices, and (iv) implement our algorithms and experimentally show that their performance is asymptotically much better than their theoretical worst-case upper bound.