We give efficient solutions to transportation problems motivated by the following robotics problem.  A robot arm has the task of rearranging m objects between n stations in the plane.  Each object is initially at one of these n stations and needs to be moved to another station.  The robot arm consists of a single link that rotates about a fixed pivot.  The link can extend in and out (like a telescope) so that its length is a variable.  At the end of this “telescoping” link lies a gripper that is capable of grasping any one of the m objects (the gripper cannot be holding mre than one object at the same time).  The robot arm must transport each of the m objects to its destination and come back to where it started.  Since the problem of scheduling the motion of the gripper so as to minimize the total distance traveled in NP-hard, we focus on the problem of minimizing only the total angular motion (rotation of the link about the pivo), or only telescoping motion.  We give algorithms for two different modes of operation: (i) No-drops. No object can be dropped before its destination is reached.  (ii) With-drops.  Any objectcan be dropped at any number of intermediate points.  Our algorithm for case (i) runs in O(m + n log n)  time for angular motion and in O(m + n alpha(n)) time for telescoping motion.  Our algorithm for case (ii) runs in O(m + n) time for angular motion and with the same time bound for telescoping motion.  The most interesting problem turns out to be that of minimizing angular motion for the with-drops mode of operation.

Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems.  The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location.  Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point.  All of the algorithms presented run in O (log n) time with either a linear or a sublinear number of processors in the CREW PRAM model.

his paper describes how anonymity is achieved in GNUnet, a framework for anonymous distributed and secure networking.

We describe GAP, a simple protocol for anonymous transfer of data which can achieve better anonymity guarantees than traditional indirection schemes and is additionally more efficient. While the building blocks of our technique are similar to previous work, we offer a new perspective on how to perceive and measure anonymity. Based on this new perspective we are able to modify the protocol to allow individual nodes to trade anonymity for efficiency.