Alon Efrat

SODA Conference 2007 Conference Paper

Restricted strip covering and the sensor cover problem

• Adam L. Buchsbaum
• Alon Efrat
• Shaili Jain
• Suresh Venkatasubramanian
• Ke Yi 0001

SODA Conference 2004 Conference Paper

On finding a guard that sees most and a shop that sells most

• Otfried Schwarzkopf
• Alon Efrat
• Sariel Har-Peled

SODA Conference 2003 Conference Paper

Matching planar maps

• Helmut Alt
• Alon Efrat
• Günter Rote
• Carola Wenk

ICRA Conference 2003 Conference Paper

Optimal strategies to track and capture a predictable target

• Alon Efrat
• Héctor H. González-Baños
• Stephen G. Kobourov
• Lingeshwaran Palaniappan

We present an O(nlog/sup 1+/spl epsiv// n)-time algorithm for computing the optimal robot motion that maintains line-of-sight visibility between a target moving inside a polygon with n vertices which may contain holes. The motion is optimal for the tracking robot (the observer) in the sense that the target either remains visible for the longest possible time, or it is captured by the observer in the minimum time when feasible. Thus, the algorithm maximizes the minimum time-to-escape. Our algorithm assumes that the target moves along a known path. Thus, it is an off-line algorithm. Our theoretical results for the algorithm's runtime assume that the target is moving along a shortest path from its source to its destination. This assumption, however is not required to prove the optimality of the computed solution, hence the algorithm remains correct for the general case.

STOC Conference 2003 Conference Paper

Touring a sequence of polygons

• Moshe Dror
• Alon Efrat
• Anna Lubiw
• Joseph S. B. Mitchell

Given a sequence of k polygons in the plane, a start point s , and a target point, t , we seek a shortest path that starts at s , visits in order each of the polygons, and ends at t . If the polygons are disjoint and convex, we give an algorithm running in time O(kn log (n/k)) , where n is the total number of vertices specifying the polygons. We also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses O(nk 2 log n) time. Our methods are simple and allow shortest path queries from s to a query point t to be answered in time O(k log n + m) , where m is the combinatorial path length. We show that for nonconvex polygons this "touring polygons" problem is NP-hard.The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in O(n 2 log n) time and the watchman route problem (through a fixed point s ) in time O(n 3 log n) , compared with the previous time bounds of O(n 3 ) and O(n 4 ) , respectively.

SODA Conference 2002 Conference Paper

Covering shapes by ellipses

• Alon Efrat
• Frank Hoffmann 0002
• Christian Knauer
• Klaus Kriegel
• Günter Rote
• Carola Wenk

SODA Conference 2001 Conference Paper

Morphing between polylines

• Alon Efrat
• Sariel Har-Peled
• Leonidas J. Guibas
• T. M. Murali 0001

SODA Conference 2001 Conference Paper

Pattern matching for sets of segments

• Alon Efrat
• Piotr Indyk
• Suresh Venkatasubramanian

SODA Conference 2000 Conference Paper

On incremental rendering of silhouette maps of polyhedral scene

• Alon Efrat
• Leonidas J. Guibas
• Olaf A. Hall-Holt
• Li Zhang 0001

SODA Conference 2000 Conference Paper

Sweeping simple polygons with a chain of guards

• Alon Efrat
• Leonidas J. Guibas
• Sariel Har-Peled
• David C. Lin
• Joseph S. B. Mitchell
• T. M. Murali 0001

FOCS Conference 1999 Conference Paper

Efficient Regular Data Structures and Algorithms for Location and Proximity Problems

• Arnon Amir
• Alon Efrat
• Piotr Indyk
• Hanan Samet

Investigates data structures obtained by a recursive partitioning of the input domain into regions of equal size. One of the most well-known examples of such a structure is the quadtree, which is used in this paper as a basis for more complex data structures; we also provide multidimensional versions of the stratified tree of P. van Emde Boas (1997). We show that, under the assumption that the input points have limited precision (i. e. are drawn from an integer grid of size u), these data structures yield efficient solutions to many important problems. In particular, they allow us to achieve O(log log u) time per operation for finding the dynamic approximate nearest neighbor (under insertions and deletions) and the exact online closest pair (under insertions only) in any constant dimension. They allow O(log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear-time (optimal) algorithm for computing the expansion of a shape represented by a quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the dilation by a ball operation.

SODA Conference 1994 Conference Paper

A Near-Linear Algorithm for the Planar Segment Center Problem

• Alon Efrat
• Micha Sharir