Improved Approximation Algorithms for Relay Placement (2009)
Alon Efrat, Sándor P. Fekete, A R. Gaddehosur, Valentin Polishchuk, Jukka Suomela
Abstract. In the relay placement problem the input is a set of sensors and a number r ≥ 1, the communication range of a relay. In the one-tier version of the problem the objective is to place a...
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled
We introduce two new related metrics, the geodesic width and the link width, for measuring the “distance ” between two non-intersecting polylines in the plane. If the two polylines have n...
Onroad Vehicular Broadcast (2009)
This paper presents a broadcasting algorithm that considerably reduces the number of retransmissions in applications such as onroad vehicular broadcasting where nodes are assumed to be arranged on a...
Shortest Tour of a Sequence of Disjoint Segments in L1 (2008)
Esther Arkin, Alon Efrat, Cesim Erten, Ferran Hurtado, Joseph Mitchell
Abstract Given a sequence s1,..., sK of K disjoint segments in the plane, a start point s and a target point t, we seek a path, that starts at s, visits in order each of the segments, and ends at t,...
Robert Kraft, Mindy M. Escobar, Martha L. Narro, Jackie L. Kurtis, Alon Efrat, Kobus Barnard, ...
Subtle cellular phenotypes in the CNS may evade detection by routine histopathology. Here, we demonstrate the value of primary culture for revealing genetically determined neuronal phenotypes at high...
On the Union of ^-Round Objects in Three and Four Dimensions* (2008)
Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir
Abstract A compact body c in Rd is ^-round if for every point p 2
Matching Planar Maps Helmut Alt \Lambda (2008)
y Abstract The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g. computer vision, geographic information...
Alon Efrat, Suresh Venkatasubramanian, Quanfu Fan
The problem of curve matching appears in many application domains, like time series analysis, shape matching, speech recognition, and signature verification, among others. Curve matching has been...
Christian A. Duncan, Alon Efrat, Stephen Kobourov, Carola Wenk
Communicated by Editor’s name Traditionally, graph drawing algorithms represent vertices as circles and edges as curves connecting the vertices. We introduce the problem of drawing with “fat ”...
On Geometric Stable Roommates and Minimum-Weight Matching Robustness (Extended Abstract) ∗ (2008)
Valentin Polishchuk, Esther M. Arkin, Kobus Barnard, Kevin Coogan, Alon Efrat, ...
Abstract This paper consists of two parts, both of which address stability of perfect matchings. In the first part we consider instances of the Stable Roommates problem that arise from geometric...
Alon Efrat, Suresh Venkatasubramanian, Quanfu Fan
The problem of curve matching appears in many application domains, like time series analysis, shape matching, speech recognition, and signature verification, among others. Curve matching has been...
A force-directed approach to sensor localization (2008)
Alon Efrat, David Forrester, Stephen G. Kobourov, Cesim Erten
We consider the centralized, anchor-free sensor localization problem. We consider the case where the sensor network reports range information and the case where in addition to the range, we also have...
Computing Homotopic Shortest Paths Efficiently (2008)
Alon Efrat, Stephen G. Kobourov, Anna Lubiw
We give algorithms to find shortest paths homotopic to given disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k log n+n √n), and...
On the Union of kappa-Curved Objects (2007)
A (not necessarily convex) object C in the plane is - curved for some constant , ! 1, if it has constant description complexity, and for each point p on the boundary of C, one can place a disk B...
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, T. M. Murali
We introduce two new related metrics, the geodesic width and the link width, for measuring the \distance " between two non-intersecting polylines in the plane. If the two polylines have n...
COVER FEATURE Using and Determining Location in a Context- Sensitive Tour Guide (2007)
In a study that provided unique insights into the challenges associated with developing location-based applications, the Lancaster Guide project used members of the general public to test a...
guidance, and numerous contributions to this work. (2007)
Sariel Har-peled, Prof Micha Sharir, Bernard Chazelle, Ken Clarkson, Alon Efrat, Jeff Erickson
by
The design of fiducials for precise image registration is of major practical importance in computer vision, especially in automatic inspection applications. We analyze the subpixel registration...
Christian A. Duncan, Alon Efrat, Stephen G. Kobourov, Carola Wenk
Abstract. In this paper, we introduce the problem of drawing with "fat " edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves...
E#cient Regular Data Structures and Algorithms for Dilation, Location and Proximity Problems (2007)
Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet
In this paper we investigate 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...
tracking — efficient proximity detection among mobile friends
On Finding a Guard that Sees Most and a Shop that Sells Most (2007)
Cheong, Otfried, Efrat, Alon, Har-Peled, Sariel
We present a near-quadratic time algorithm that computes a point inside a simple polygon P in the plane having approximately the largest visibility polygon inside P, and a near-linear time algorithm...
Restricted strip covering and the sensor cover problem (2007)
Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, Ke Yi
Suppose we are given a set of objects that cover a region and a duration associated with each object. Viewing the objects as jobs, can we schedule their beginning times to maximize the length of time...
Restricted strip covering and the sensor cover problem (2007)
Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, Ke Yi
Suppose we are given a set of objects that cover a region and a duration associated with each object. Viewing the objects as jobs, can we schedule their beginning times to maximize the length of time...
Valentin Polishchuk, Esther M. Arkin, Kobus Barnard, Kevin Coogan, Alon Efrat, ...
We introduce the notion of robustness of the minimum-weight perfect matching. The robustness measures how much the edge weights of a graph are allowed to change before the minimum-weight matching...
Geometric Stable Roommates (2007)
Esther M. Arkin, Alon Efrat, Valentin Polishchuk
We consider instances of the Stable Roommates problem that arise from geometric representation of participants preferences: a participant is a point in a metric space, and his preference list is...
Restricted Strip Covering and the Sensor Cover Problem (2006)
Buchsbaum, Adam L., Efrat, Alon, Jain, Shaili, Venkatasubramanian, Suresh, Yi, Ke
Given a set of objects with durations (jobs) that cover a base region, can we schedule the jobs to maximize the duration the original region remains covered? We call this problem the sensor cover...
Coverage time characteristics in sensor networks (2006)
Ravi Balasubramanian, Srinivasan Ramasubramanian, Alon Efrat
Abstract — We study the problem of coverage of a given area for a maximum duration using a set of batteryoperated sensors. Each sensor has a fixed sensing range and a limited lifetime due to the...
Geometric Approaches to Ad Hoc and Sensor Networks: Full Report of the 2006 NSF Workshop (2006)
Subhash Suri, Alon Efrat, Leonidas J. Guibas
Embedded networked sensing devices are becoming ubiquitous across many activities that are important to our economy and life, from manufacturing and industrial sensing, to agriculture and...
Matching slides to presentation videos using sift and scene background matching (2006)
Quanfu Fan, Alon Efrat, Ming Lin
We present a general approach for automatically matching electronic slides to videos of corresponding presentations for use in distance learning and video proceedings of conferences. We deal with a...
Guarding galleries and terrains (2006)
Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation...
Force-Directed Approaches to Sensor Network Localization (2006)
Kobourov, Stephen G., Efrat, Alon, Forrester, David, Iyer, Anand
In many sensor network applications it is necessary to compute low-error localization of the sensor nodes. Although embedding a GPS unit on each node would solve the problem for many outdoor...
S.: Hardwareassisted natural neighbor interpolation (2005)
Quanfu Fan, Alon Efrat, Vladlen Koltun, Shankar Krishnan, Suresh Venkatasubramanian
Natural neighbor interpolation is a weighted average interpolation method that is based on Voronoi tessellation. In this paper, we present and implement an algorithm to perform natural neighbor...
Approximation algorithms for two optimal location problems in sensor networks (2005)
This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of...
Approximation algorithms for two optimal location problems in sensor networks (2005)
Abstract — This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network...
S.: Hardwareassisted natural neighbor interpolation (2005)
Quanfu Fan, Alon Efrat, Vladlen Koltun, Shankar Krishnan, Suresh Venkatasubramanian
Natural neighbor interpolation is a weighted average interpolation method that is based on Voronoi tessellation. In this paper, we present and implement an algorithm to perform natural neighbor...
Approximation algorithms for two optimal location problems in sensor networks (2005)
This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of...
Fixed-Location Circular-Arc Drawing of Planar Graphs (2004)
Efrat, Alon, Erten, Cesim, Kobourov, Stephen G.
In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of n points on the plane, where n...
Fixed-Location Circular-Arc Drawing of Planar Graphs (2004)
Efrat, Alon, Erten, Cesim, Kobourov, Stephen G.
In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of n points on the plane, where n...
Fixed-Location Circular-Arc Drawing of Planar Graphs (2004)
Efrat, Alon, Erten, Cesim, Kobourov, Stephen G.
In this paper we consider the problem of drawing a planar graph using circular-arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of n points on the plane, where n...
On finding a guard that sees most and a shop that sells most (2004)
Otfried Cheong, Alon Efrat, Sariel Har-peled
We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and near-linear time algorithm for nding the...
On the union of κ-round objects in three and four dimensions (2004)
Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir
A compact set c in R d is κ-round if for every point p ∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ> 0, the...
On the Union of ^-Round Objects in Three and Four Dimensions* (2004)
Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir
Abstract A compact body c in Rd is ^-round if for every point p 2 @c there exists a closed ball that contains p, is contained in c, and has radius ^ diam c. We show that, for any fixed ^> 0, the...
Buddy tracking - efficient proximity detection among mobile friends (2004)
Arnon Amir, Alon Efrat, Jussi Myllymaki, Kevin Wampler, Arnon Amir, Alon Efrat, ...
friends
Approximation Algorithms for Two Optimal Location Problems in Sensor Networks (2004)
This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of...
On finding a guard that sees most and a shop that sells most (2004)
Otfried Cheong, Alon Efrat, Sariel Har-peled
We present a near-quadratic time algorithm that computes a point inside a simple polygon P in the plane having approximately the largest visibility polygon inside P, and a near-linear time algorithm...
On the union of κ-round objects in three and four dimensions (2004)
Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir
A compact body c in R d is κ-round if for every point p ∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ> 0, the...
On finding a guard that sees most and a shop that sells most (2004)
Otfried Cheong, Alon Efrat, Sariel Har-peled
We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and a nearlinear time algorithm for finding...
Buddy tracking - efficient proximity detection among mobile friends (2004)
Arnon Amir, Alon Efrat, Jussi Myllymaki, Kevin Wampler
Abstract: Global positioning systems (GPS) and mobile phone networks are making it possible to track individual users with an increasing accuracy. It is natural to ask whether this information can be...
On finding a guard that sees most and a shop that sells most (2004)
Otfried Cheong, Alon Efrat, Sariel Har-peled
We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and a nearlinear time algorithm for finding...
Search the Audio, Browse the Video—A Generic Paradigm for Video Collections (2003)
Arnon Amir, Savitha Srinivasan, Alon Efrat
The amount of digital video being shot, captured, and stored is growing at a rate faster than ever before. The large amount of stored video is not penetrable without efficient video indexing,...
DOI: 10.1007/s00453-003-1047-0 Covering with Ellipses 1 (2003)
Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk
Abstract. We address the problem of how to cover a set of required points by a small number of axis-parallel ellipses that avoid a second set of forbidden points. We study geometric properties of...
DOI: 10.1007/s00453-003-1047-0 Covering with Ellipses 1 (2003)
Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk
Abstract. We address the problem of how to cover a set of required points by a small number of axis-parallel ellipses that avoid a second set of forbidden points. We study geometric properties of...
Touring a sequence of polygons (2003)
Moshe Dror, Alon Efrat, Anna Lubiw
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...
Finding a Curve in a Map (2003)
Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, Günter Rote
Given a polygonal curve and a geometric graph, we describe an e#cient algorithm to find a path in the graph which is most similar to the curve, using the well-known Frechet distance for curves.
Finding a Curve in a Map (2003)
Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, Günter Rote
Given a polygonal curve and a geometric graph, we describe an ecient algorithm to nd a path in the graph which is most similar to the curve, using the well-known Frechet distance for curves.
Helmut Alt, Alon Efrat, Günter Rote, Carola Wenk
The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g., computer vision, geographic information systems, etc....
Optimal Strategies to Track and Capture a Predictable Target (2003)
Alon Efrat Ector, Alon Efrat, Stephen G. Kobourov
We present an O(n log for computing the optimal robot motion that maintains lineof -sight visibility between a target moving inside a polygon with n vertices which may contain holes. The motion is...
Helmut Alt, Alon Efrat, Günter Rote, Carola Wenk
The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g. computer vision, geographic information systems, etc. More...
Fixed-location circular-arc drawing of planar graphs (2003)
Alon Efrat, Cesim Erten, Stephen G. Kobourov
Abstract. In this paper we consider the problem of drawing a planar graph using circular-arcs as edges and given a one-to-one mapping between the vertices of the graph and a set of n points on the...
Finding a Curve in a Map (2003)
Carola Wenk, Helmut Alt, Alon Efrat, Lingeshwaran Palaniappan, Günter Rote
Given a polygonal curve and a geometric graph, we describe an ecient algorithm to nd a path in the graph which is most similar to the curve, using the well-known Frechet distance for curves.
Fixed-location circular-arc drawing of planar graphs (2003)
Alon Efrat, Cesim Erten, Stephen G. Kobourov
In this paper we consider the problem of drawing a planar graph using circular arcs as edges, given a one-to-one mapping between the vertices of the graph and a set of points in the plane. If for...
Search the Audio, Browse the Video—A Generic Paradigm for Video Collections (2003)
Alon Efrat, Savitha Srinivasan, Arnon Amir
The amount of digital video being shot, captured, and stored is growing at a rate faster than ever before. The large amount of stored video is not penetrable without efficient video indexing,...
Search the Audio, Browse the Video—A Generic Paradigm for Video Collections (2003)
Arnon Amir, Savitha Srinivasan, Alon Efrat
The amount of digital video being shot, captured, and stored is growing at a rate faster than ever before. The large amount of stored video is not penetrable without efficient video indexing,...
Computing Homotopic Shortest Paths Efficiently (2002)
Efrat, Alon, Kobourov, Stephen G., Lubiw, Anna
This paper addresses the problem of finding shortest paths homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm than previously...
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
Duncan, Christian A., Efrat, Alon, Kobourov, Stephen G., Wenk, Carola
In this paper, we introduce the problem of drawing with "fat" edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the vertices. In this...
Computing homotopic shortest paths efficiently (2002)
Alon Efrat, Stephen G. Kobourov, Anna Lubiw
Geometric shortest paths are a major topic in computational geometry; see the survey paper by Mitchell [12]. A shortest path between two points in a simple polygon can be found in linear time using...
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, T. M. Murali
We introduce two new related metrics, the geodesic width and the link width, for measuring the “distance ” between two non-intersecting polylines in the plane. If the two polylines have n...
Geometry helps in bottleneck matching and related problems (2001)
Alon Efrat, Alon Itai, Matthew J. Katz
This paper is accepted for publication in ALGORITHMICA Abstract Let A and B be two sets of n objects in Rd, and let Match be a (one-to-one)matching between A and B. Let min(Match), max(Match), and...
Christian A. Duncan, Alon Efrat, Stephen G. Kobourov, Carola Wenk
Abstract. In this paper, we introduce the problem of drawing with “fat ” edges. Traditionally, graph drawing algorithms represent vertices as circles and edges as closed curves connecting the...
Alon Efrat, Frank Hoffmann, Alon Efrat, Christian Knauer, Günter Rote, Christian Knauer, ...
We address the problem of how to cover a set of required points by a small number of axis{parallel ellipses that avoid a second set of forbidden points. We study geometric properties of such covers...
Pattern matching for sets of segments (2001)
Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian
In this paper we present algorithms for a number of problems in geometric pattern matching where the input consists of a collection of orthogonal segments in the plane. Such collections arise...
Geometric algorithms for the analysis of 2d-electrophoresis gels (2001)
Alon Efrat, Frank Hoffmann, Ý Klaus, Kriegel Ýþü, Christof Schultz Ýü, Carola Wenk Ýß
In proteomics 2–dimensional gel electrophoresis (2–DE) is a separation technique for proteins. The resulting protein spots can be identified by either using picking robots and subsequent mass...
Pattern Matching for sets of segments (2000)
Efrat, Alon, Indyk, Piotr, Venkatasubramanian, Suresh
In this paper we present algorithms for a number of problems in geometric pattern matching where the input consist of a collections of segments in the plane. Our work consists of two main parts. In...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
Abstract We consider the problem of locating a continuously-moving target using a group of guardsmoving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
Abstract We consider the problem of locating a moving target using a group of guards cooperatively moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon...
On incremental rendering of silhouette maps of a polyhedral scene (2000)
Alon Efrat, Leonidas J. Guibas, Li Zhang
We consider the problem of incrementally rendering a polyhedral scene while the viewpoint is moving. In practical situations the number of geometric primitives to be rendered can be very large---...
Sweeping Simple Polygons with a Chain of Guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin, T. M. Murali
We consider the problem of locating a continuously-moving target using a group of guards moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Sweeping Simple Polygons with a Chain of Guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin, T. M. Murali
We consider the problem of locating a moving target using a group of guards cooperatively moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Morphing between Polylines (2000)
Alon Efrat, Sariel Har-peled, Leonidas J. Guibas, T. M. Murali
We study the problem of continuously transforming or morphing two non-intersecting simple (not self-intersecting) polylines in the plane. Our morphing strategies have the property that every...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
We consider the problem of locating a continuously-moving target using a group of guards moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Geometric Approximation Algorithms and Randomized Algorithms for Planar Arrangements (1999)
Prof Micha Sharir, Hervé Brönnimann, Bernard Chazelle, Ken Clarkson, Alon Efrat, Jeff Erickson, ...
by
The complexity of the union of (#, #)-covered objects (1999)
An (#, #)-covered object is a simply connected planar region c with the property that for each point p #c there exists a triangle contained in c and having p as a vertex, such that all its angles are...
Geometry Helps in Bottleneck Matching and Related Problems (1999)
Alon Efrat, Alon Itai, Matthew J. Katz
Let A and B be two sets of n objects in R d , and let Match be a (one-to-one) matching between A and B. Let min(Match), max(Match), and \Sigma(Match) denote the length of the shortest edge, the...
Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications (1999)
Pankaj K. Agarwal, Alon Efrat, Micha Sharir
Abstract Let F be a collection of n bivariate algebraic functions of constant maximum degree.We show that the combinatorial complexity of the vertical decomposition of the <= k-levelof the...
Fly Cheaply: On the Minimum Fuel-Consumption Problem (1998)
Introduction Assume we wish to plan a path of a flight, starting at an airport s (i.e. Tel-Aviv), and our destination is the airport t (i.e. Minneapolis). Our plane is able to carry enough fuel, so a...
On the Number of Regular Vertices of the Union of Jordan Regions (1998)
Boris Aronov, Alon Efrat, Dan Halperin, Micha Sharir
Let C be a collection of n Jordan regions in the plane in general position, such that each pair of their boundaries intersect in at most s points, where s is a constant. Let U denote the union of C....
Separating and Shattering Long Line Segments (1997)
Efrat, Alon, Schwarzkopf, Otfried
A line l is called a separator for a set S of objects in the plane if l avoids all the objects and partitions S into two non-empty subsets, lying on both sides of l. A set L of lines is said to...
Separating and Shattering Long Line Segments (1997)
Alon Efrat, Otfried Schwarzkopf
this paper we consider the problem of finding separators for a set of line-segments. Clearly this is sufficient to treat the case of general polygonal objects as well.
On the Complexity of the Union of Fat Objects in (1997)
The Plane Alon, Alon Efrat, Micha Sharir
We prove a near-linear bound on the combinatorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times.
Separating and shattering long line segments (1997)
Alon Efrat, Otfried Schwarzkopf
A line l is called a separator for a set S of objects in the plane if l avoids all the objects and partitions S into two non-empty subsets, lying on both sides of l. A set L of lines is said to...
A Near-Linear Algorithm for the Planar Segment Center Problem (1996)
Let P be a set of n points in the plane and let e be a segment of fixed length. The segment center problem is to find a placement of e (allowing translation and rotation) which minimizes the maximum...
Computing fair and bottleneck matchings in geometric graphs (1996)
Let A and B be two sets of n points in the plane, and let M be a (one-to-one) matching between A and B. Let min(M), max(M), and \Sigma(M) denote the length of the shortest edge, the length of the...
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications (1996)
Pankaj K. Agarwal, Alon Efrat, Micha Sharir
Let F be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the k-level of the arrangement A(F) is...
Improvements on Bottleneck Matching and Related Problems Using Geometry (1996)
Alon Efrat, Alon Itai, Matthew J. Katz
Let A and B be two sets of n objects in R d , and let M be a (one-to-one) matching between A and B. Let min(M ), max(M ), and \Sigma(M ) denote the length of the shortest edge, the length of the...
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications (1995)
Alon Efrat, Micha Sharir, Pankaj K. Agarwal, Pankaj K. Agarwal
Let F be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the k-level of the arrangement A(F) is...
Geometric Pattern Matching (1995)
In Dimensional Space, L. Paul Chew, Dorit Dor, Alon Efrat, Klara Kedem
We show that, using the L1 metric, the minimum Hausdorff distance under translation between two point sets of cardinality n in d-dimensional space can be computed n) for 3 ! d 8, and in time O(n n)...
Efficient Regular Data Structures and Algorithms for Location and Proximity Problems
Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet
In this paper we investigate 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...
Geometric Pattern Matching in d-Dimensional Space
L. Paul Chew, Dorit Dor, Alon Efrat, Klara Kedem
We show that, using the L1 metric, the minimum Hausdorff distance under translation between two point sets of cardinality n in d-dimensional space can be computed in time O(n (4d\Gamma2)=3 log 2 n)...
Geometric Pattern Matching in d-Dimensional Space
L. Paul Chew, Dorit Dor, Alon Efrat, Klara Kedem
. We show that, using the L1 metric, the minimum Hausdorff distance under translation between two point sets of cardinality n in d- dimensional space can be computed in time O(n (4d\Gamma2)=3 log 2...