Publications (10)
Minimum-Length Coordinated Motions For Two Convex Centrally-Symmetric Robots
David Kirkpatrick, Paul Liu
We study the problem of determining coordinated motions, of minimum total length, for two arbitrary convex centrally-symmetric (CCS) robots in an otherwise obstacle-free plane. Usi…
Absolute and arbitrary orientation of single molecule shapes
Ashwin Gopinath, Chris Thachuk, Anya Mitskovets +3
DNA origami is a modular platform for the combination of molecular and colloidal components to create optical, electronic, and biological devices. Integration of such nanoscale dev…
Discrete Dubins Paths
Sylvester Eriksson-Bique, David Kirkpatrick, Valentin Polishchuk
A Dubins path is a shortest path with bounded curvature. The seminal result in non-holonomic motion planning is that (in the absence of obstacles) a Dubins path consists either fro…
Improved Approximation for Guarding Simple Galleries from the Perimeter
James King, David Kirkpatrick
We provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for buil…
Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility
David Kirkpatrick, Irina Kostitsyna, Alfredo Navarra +2
Among fundamental problems in the context of distributed computing by autonomous mobile entities, one of the most representative and well studied is {\sc Point Convergence}: given…
Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil +5
We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices ca…
Frequency-Competitive Query Strategies to Maintain Low Congestion Potential Among Moving Entities
William Evans, David Kirkpatrick
We consider the problem of using location queries to monitor the congestion potential among a collection of entities moving, with bounded speed but otherwise unpredictably, in -…
Distance-based Learning of Hypertrees
Shaun Fallat, Kamyar Khodamoradi, David Kirkpatrick +3
We study the problem of learning hypergraphs with shortest-path queries (SP-queries), and present the first provably optimal online algorithm for a broad and natural class of hyper…
Characterizing minimum-length coordinated motions for two discs
David Kirkpatrick, Paul Liu
We study the problem of determining optimal coordinated motions for two disc robots in an otherwise obstacle-free plane. Using the total path length traced by the two disc centres…
Optimal Collusion-Free Teaching
David Kirkpatrick, Hans U. Simon, Sandra Zilles
Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-freeness was proposed by Goldman and Mat…