Alon Efrat

Interests

No activities entered.

Courses

Scholarly Contributions

Books

• Gao, J., Efrat, A., Fekete, S. P., & Zhang, Y. (2015). Algorithms for Sensor Systems: 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014, Wroclaw, Poland, September 12, 2014, Revised Selected Papers. Springer.

Chapters

• Agarwal, P. K., Efrat, A., Sharathkumar, R., & Yu, H. (2009). On Approximate Geodesic-Distance Queries amid Deforming Point Clouds. In Algorithmic Foundation of Robotics VIII(pp 351--365). Springer Berlin Heidelberg.
• Gonz\'alez-Ba\~nos, H., Mao, E., Latombe, J., Murali, T. M., & Efrat, A. (2000). Planning robot motion strategies for efficient model construction. In Robotics Research(pp 345--352). Springer, London.

Journals/Publications

• , A. E., , P. I., & , S. V. (2022). Pattern Matching for sets of segments.
  More info

  In this paper we present algorithms for a number of problems in geometricpattern matching where the input consist of a collections of segments in theplane. Our work consists of two main parts. In the first, we address problemsand measures that relate to collections of orthogonal line segments in theplane. Such collections arise naturally from problems in mapping buildings androbot exploration. We propose a new measure of segment similarity called a \emph{coveragemeasure}, and present efficient algorithms for maximising this measure betweensets of axis-parallel segments under translations. Our algorithms run in time$O(n^3\polylog n)$ in the general case, and run in time $O(n^2\polylog n)$ forthe case when all segments are horizontal. In addition, we show that whenrestricted to translations that are only vertical, the Hausdorff distancebetween two sets of horizontal segments can be computed in time roughly$O(n^{3/2}{\sl polylog}n)$. These algorithms form significant improvements overthe general algorithm of Chew et al. that takes time $O(n^4 \log^2 n)$. In thesecond part of this paper we address the problem of matching polygonal chains.We study the well known \Frd, and present the first algorithm for computing the\Frd under general translations. Our methods also yield algorithms forcomputing a generalization of the \Fr distance, and we also present a simpleapproximation algorithm for the \Frd that runs in time $O(n^2\polylog n)$.[Journal_ref: ]
• , A. E., , S. G., & , A. L. (2022). Computing Homotopic Shortest Paths Efficiently.
  More info

  This paper addresses the problem of finding shortest paths homotopic to agiven disjoint set of paths that wind amongst point obstacles in the plane. Wepresent a faster algorithm than previously known.[Journal_ref: ]
• , A. L., , A. E., , S. J., , S. V., & , K. Y. (2022). Restricted Strip Covering and the Sensor Cover Problem.
  More info

  Given a set of objects with durations (jobs) that cover a base region, can weschedule the jobs to maximize the duration the original region remains covered?We call this problem the sensor cover problem. This problem arises in thecontext of covering a region with sensors. For example, suppose you wish tomonitor activity along a fence by sensors placed at various fixed locations.Each sensor has a range and limited battery life. The problem is to schedulewhen to turn on the sensors so that the fence is fully monitored for as long aspossible. This one dimensional problem involves intervals on the real line.Associating a duration to each yields a set of rectangles in space and time,each specified by a pair of fixed horizontal endpoints and a height. Theobjective is to assign a position to each rectangle to maximize the height atwhich the spanning interval is fully covered. We call this one dimensionalproblem restricted strip covering. If we replace the covering constraint by apacking constraint, the problem is identical to dynamic storage allocation, ascheduling problem that is a restricted case of the strip packing problem. Weshow that the restricted strip covering problem is NP-hard and present an O(loglog n)-approximation algorithm. We present better approximations or exactalgorithms for some special cases. For the uniform-duration case of restrictedstrip covering we give a polynomial-time, exact algorithm but prove that theuniform-duration case for higher-dimensional regions is NP-hard. Finally, weconsider regions that are arbitrary sets, and we present an O(logn)-approximation algorithm.[Journal_ref: ]
• , M. K., , A. M., , A. E., , V. P., & , M. C. (2022). Prediction and Prevention of Pandemics via Graphical Model Inference and Convex Programming.
  More info

  Hard-to-predict bursts of COVID-19 pandemic revealed significance ofstatistical modeling which would resolve spatio-temporal correlations overgeographical areas, for example spread of the infection over a city with censustract granularity. In this manuscript, we provide algorithmic answers to thefollowing two inter-related public health challenges. (1) Inference Challenge:assuming that there are $N$ census blocks (nodes) in the city, and given aninitial infection at any set of nodes, what is the probability for a subset ofcensus blocks to become infected by the time the spread of the infection burstis stabilized? (2) Prevention Challenge: What is the minimal control action onecan take to minimize the infected part of the stabilized state footprint? Toanswer the challenges, we build a Graphical Model of pandemic of the attractiveIsing (pair-wise, binary) type, where each node represents a census track andeach edge factor represents the strength of the pairwise interaction between apair of nodes. We show that almost all attractive Ising Models on dense graphsresult in either of the two modes for the most probable state: either all nodeswhich were not infected initially became infected, or all the initiallyuninfected nodes remain uninfected. This bi-modal solution of the InferenceChallenge allows us to re-state the Prevention Challenge as the followingtractable convex programming: for the bare Ising Model with pair-wise and biasfactors representing the system without prevention measures, such that the MAPstate is fully infected for at least one of the initial infection patterns,find the closest, in $l_1$ norm, set of factors resulting in all the MAP statesof the Ising model, with the optimal prevention measures applied, to becomesafe.[Journal_ref: ]
• , S. S., , A. E., , S. R., & , P. K. (2022). On Channel-Discontinuity-Constraint Routing in Wireless Networks.
  More info

  Multi-channel wireless networks are increasingly being employed asinfrastructure networks, e.g. in metro areas. Nodes in these networksfrequently employ directional antennas to improve spatial throughput. In suchnetworks, given a source and destination, it is of interest to compute anoptimal path and channel assignment on every link in the path such that thepath bandwidth is the same as that of the link bandwidth and such a pathsatisfies the constraint that no two consecutive links on the path are assignedthe same channel, referred to as "Channel Discontinuity Constraint" (CDC).CDC-paths are also quite useful for TDMA system, where preferably everyconsecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an $O(N^{2})$distributed algorithm for discovering the shortest CDC-path between givensource and destination. This improves the running time of the $O(N^{3})$centralized algorithm of Ahuja et al. for finding the minimum-weight CDC-path.Our second result is a generalized $t$-spanner for CDC-path; For any $\theta>0$we show how to construct a sub-network containing only $O(\frac{N}{\theta})$edges, such that that length of shortest CDC-paths between arbitrary sourcesand destinations increases by only a factor of at most$(1-2\sin{\tfrac{\theta}{2}})^{-2}$. We propose a novel algorithm to computethe spanner in a distributed manner using only $O(n\log{n})$ messages. Animportant conclusion of this scheme is in the case of directional antennas areused. In this case, it is enough to consider only the two closest nodes in eachcone.[Journal_ref: ]
• , A. E., , R. F., , S. K., & , C. D. (2021). Polygons with Prescribed Angles in 2D and 3D.
  More info

  We consider the construction of a polygon $P$ with $n$ vertices whose turningangles at the vertices are given by a sequence $A=(\alpha_0,\ldots,\alpha_{n-1})$, $\alpha_i\in (-\pi,\pi)$, for $i\in\{0,\ldots, n-1\}$. Theproblem of realizing $A$ by a polygon can be seen as that of constructing astraight-line drawing of a graph with prescribed angles at vertices, and hence,it is a special case of the well studied problem of constructing an \emph{anglegraph}. In 2D, we characterize sequences $A$ for which every generic polygon$P\subset \mathbb{R}^2$ realizing $A$ has at least $c$ crossings, for every$c\in \mathbb{N}$, and describe an efficient algorithm that constructs, for agiven sequence $A$, a generic polygon $P\subset \mathbb{R}^2$ that realizes $A$with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence$A$ can be realized by a (not necessarily generic) polygon $P\subset\mathbb{R}^3$, and for every realizable sequence the algorithm finds arealization.[Journal_ref: ]
• , A. E., , S. P., , J. S., , V. P., & , J. S. (2021). Improved Approximation Algorithms for Relay Placement.
  More info

  In the relay placement problem the input is a set of sensors and a number $r\ge 1$, the communication range of a relay. In the one-tier version of theproblem the objective is to place a minimum number of relays so that betweenevery pair of sensors there is a path through sensors and/or relays such thatthe consecutive vertices of the path are within distance $r$ if both verticesare relays and within distance 1 otherwise. The two-tier version adds therestrictions that the path must go through relays, and not through sensors. Wepresent a 3.11-approximation algorithm for the one-tier version and a PTAS forthe two-tier version. We also show that the one-tier version admits no PTAS,assuming P $\ne$ NP.[Journal_ref: ]
• , A. R., , F. D., , S. D., , A. E., , M. I., , S. K., , J. L., , S. A., & , E. W. (2021). L-Graphs and Monotone L-Graphs.
  More info

  In an $\mathsf{L}$-embedding of a graph, each vertex is represented by an$\mathsf{L}$-segment, and two segments intersect each other if and only if thecorresponding vertices are adjacent in the graph. If the corner of each$\mathsf{L}$-segment in an $\mathsf{L}$-embedding lies on a straight line, wecall it a monotone $\mathsf{L}$-embedding. In this paper we give a fullcharacterization of monotone $\mathsf{L}$-embeddings by introducing a new classof graphs which we call "non-jumping" graphs. We show that a graph admits amonotone $\mathsf{L}$-embedding if and only if the graph is a non-jumpinggraph. Further, we show that outerplanar graphs, convex bipartite graphs,interval graphs, 3-leaf power graphs, and complete graphs are subclasses ofnon-jumping graphs. Finally, we show that distance-hereditary graphs and$k$-leaf power graphs ($k\le 4$) admit $\mathsf{L}$-embeddings.[Journal_ref: ]
• , F. D., , A. E., , S. K., , S. K., & , R. S. (2021). Approximation algorithms for the vertex-weighted grade-of-service Steiner tree problem.
  More info

  Given a graph $G = (V,E)$ and a subset $T \subseteq V$ of terminals, a\emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weightedSteiner tree (VST) problem, each vertex is assigned a non-negative weight, andthe goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-levelgraph construction, the \emph{vertex-weighted grade-of-service Steiner treeproblem} (V-GSST), which can be stated as follows: given a graph $G$ andterminals $T$, where each terminal $v \in T$ requires a facility of a minimumgrade of service $R(v)\in \{1,2,\ldots\ell\}$, compute a Steiner tree $G'$ byinstalling facilities on a subset of vertices, such that any two verticesrequiring a certain grade of service are connected by a path in $G'$ with theminimum grade of service or better. Facilities of higher grade are more costlythan facilities of lower grade. Multi-level variants such as this one can beuseful in network design problems where vertices may require facilities ofvarying priority. While similar problems have been studied in the edge-weighted case, they havenot been studied as well in the more general vertex-weighted case. We firstdescribe a simple heuristic for the V-GSST problem whose approximation ratiodepends on $\ell$, the number of grades of service. We then generalize thegreedy algorithm of [Klein \& Ravi, 1995] to show that the V-GSST problemadmits a $(2 \ln |T|)$-approximation, where $T$ is the set of terminalsrequiring some facility. This result is surprising, as it shows that the(seemingly harder) multi-grade problem can be approximated as well as the VSTproblem, and that the approximation ratio does not depend on the number ofgrades of service.[Journal_ref: ]
• , N. M., , A. E., , D. E., , D. F., , M. G., , S. K., , P. M., & , V. P. (2021). Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains.
  More info

  We show new applications of the nearest-neighbor chain algorithm, a techniquethat originated in agglomerative hierarchical clustering. We apply it to adiverse class of geometric problems: we construct the greedy multi-fragmenttour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and forSteiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we computemotorcycle graphs (which are a central part in straight skeleton algorithms) in$O(n^{4/3+\varepsilon})$ time for any $\varepsilon>0$; we introduce anarcissistic variant of the $k$-attribute stable matching model, and solve itin $O(n^{2-4/(k(1+\varepsilon)+2)})$ time; we give a linear-time$2$-approximation for a 1D geometric set cover problem with applications toradio station placement.[Journal_ref: ]
• , R. A., , P. A., , F. D., , A. E., , D. G., , M. G., , N. H., , S. G., , R. S., , J. W., & , A. W. (2021). Multi-Level Steiner Trees.
  More info

  In the classical Steiner tree problem, given an undirected, connected graph$G=(V,E)$ with non-negative edge costs and a set of \emph{terminals}$T\subseteq V$, the objective is to find a minimum-cost tree $E' \subseteq E$that spans the terminals. The problem is APX-hard; the best known approximationalgorithm has a ratio of $\rho = \ln(4)+\varepsilon < 1.39$. In this paper, westudy a natural generalization, the \emph{multi-level Steiner tree} (MLST)problem: given a nested sequence of terminals $T_{\ell} \subset \dots \subsetT_1 \subseteq V$, compute nested trees $E_{\ell}\subseteq \dots \subseteqE_1\subseteq E$ that span the corresponding terminal sets with minimum totalcost. The MLST problem and variants thereof have been studied under variousnames including Multi-level Network Design, Quality-of-Service Multicast tree,Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximationresults are known. We first present two simple $O(\ell)$-approximationheuristics. Based on these, we introduce a rudimentary composite algorithm thatgeneralizes the above heuristics, and determine its approximation ratio bysolving a linear program. We then present a method that guarantees the sameapproximation ratio using at most $2\ell$ Steiner tree computations. We comparethese heuristics experimentally on various instances of up to 500 verticesusing three different network generation models. We also present variousinteger linear programming (ILP) formulations for the MLST problem, and comparetheir running times on these instances. To our knowledge, the compositealgorithm achieves the best approximation ratio for up to $\ell=100$ levels,which is sufficient for most applications such as network visualization ordesigning multi-level infrastructure.[Journal_ref: ]
• , S. S., , A. E., , S. R., & , J. T. (2021). Scheduling Sensors for Guaranteed Sparse Coverage.
  More info

  Sensor networks are particularly applicable to the tracking of objects inmotion. For such applications, it may not necessary that the whole region becovered by sensors as long as the uncovered region is not too large. Thisnotion has been formalized by Balasubramanian et.al. as the problem of$\kappa$-weak coverage. This model of coverage provides guarantees about theregions in which the objects may move undetected. In this paper, we analyse thetheoretical aspects of the problem and provide guarantees about the lifetimeachievable. We introduce a number of practical algorithms and analyse theirsignificance. The main contribution is a novel linear programming basedalgorithm which provides near-optimal lifetime. Through extensiveexperimentation, we analyse the performance of these algorithms based onseveral parameters defined.[Journal_ref: ]
• , T. J., , J. V., , C. D., , M. K., , G. S., , H. R., , A. E., & , M. H. (2021). A Mobile Food Recommendation System Based on The Traffic Light Diet.
  More info

  Innovative, real-time solutions are needed to address the mismatch betweenthe demand for and supply of critical information to inform and motivate dietand health-related behavior change. Research suggests that interventions usingmobile health technologies hold great promise for influencing knowledge,attitudes, and behaviors related to energy balance. The objective of this paperis to present insights related to the development and testing of a mobile foodrecommendation system targeting fast food restaurants. The system is designedto provide consumers with information about energy density of food optionscombined with tips for healthier choices when dining out, accessible through amobile phone.[Journal_ref: ]
• , Y. P., , A. E., , M. L., , B. W., , H. Q., , J. M., , J. G., & , E. A. (2021). Data Inference from Encrypted Databases: A Multi-dimensional Order-Preserving Matching Approach.
  More info

  Due to increasing concerns of data privacy, databases are being encryptedbefore they are stored on an untrusted server. To enable search operations onthe encrypted data, searchable encryption techniques have been proposed.Representative schemes use order-preserving encryption (OPE) for supportingefficient Boolean queries on encrypted databases. Yet, recent works showed thepossibility of inferring plaintext data from OPE-encrypted databases, merelyusing the order-preserving constraints, or combined with an auxiliary plaintextdataset with similar frequency distribution. So far, the effectiveness of suchattacks is limited to single-dimensional dense data (most values from thedomain are encrypted), but it remains challenging to achieve it onhigh-dimensional datasets (e.g., spatial data) which are often sparse innature. In this paper, for the first time, we study data inference attacks onmulti-dimensional encrypted databases (with 2-D as a special case). Weformulate it as a 2-D order-preserving matching problem and explore bothunweighted and weighted cases, where the former maximizes the number of pointsmatched using only order information and the latter further considers pointswith similar frequencies. We prove that the problem is NP-hard, and thenpropose a greedy algorithm, along with a polynomial-time algorithm withapproximation guarantees. Experimental results on synthetic and real-worlddatasets show that the data recovery rate is significantly enhanced comparedwith the previous 1-D matching algorithm.[Journal_ref: ]
• Efrat, A., Fulek, R., Kobourov, S. G., & T\'{o}th, C. D. (2021). Polygons with Prescribed Angles in 2D and 3D. Journal of Graph Algorithms and Applications (JGAA).
• Ahmed, A. R., Angelini, P., Sahneh, F. D., Efrat, A., Glickenstein, D., Gronemann, M., Heinsohn, N., Kobourov, S. G., Spence, R., Watkins, J., & Wolff, A. (2019). Multi-level Steiner Trees. ACM J. Exp. Algorithmics, 24(1), 2.5:1--2.5:22.
• Agarwal, P., Efrat, A., Funke, S., Seth, G. N., Gupta, S. H., Hnat, T., Jiang, A. A., Li, Q., Liu, M., Liu, Y., & others, . (2018). DCoSS 2013 Technical Program Committee and Affiliation.
• EFRAT, A. (2018). GESTURE IDENTIFICATION AND REPLICATION.
• Efrat, A., Ezra, E., Pinchasi, R., & Sankararaman, S. (2018). Achieving Tolerance to Geographically Correlated Failures in Distributed Networked Storage⇤.
• Efrat, A., Har-peled, S., Mitchell, J. S., & others, . (2018). Approximation Algorithms for Two Optimal Location.
• Efrat, A., Li, B., Chiasserini, C., Wang, C., Bettstetter, C., Scheideler, C., Xuan, D., Calinescu, G., Ammari, H., Gupta, H., & others, . (2018). DCoSS 2015 Technical Program Committee.
• Grebla, G., Arkin, E., Cassuto, Y., Efrat, A., Mitchell, J. S., & Segal, M. (2018). Optimal Placement of Protective Jammers for Securing Wireless Transmissions in a Geographic Domain.
• Hoffmann, F., Kriegel, K., Schultz, C., & Efrat, A. (2018). Covering Shapes by Ellipses for the Computer Analysis of Protein Patterns.
• Iyer, A., Efrat, A., Erten, C., Forrester, D., & Kobourov, S. G. (2018). A Force-Directed Approach to Sensor Localization (System Demo).
• Myers, P., Sankararaman, S., & Efrat, A. (2018). Finding Moving Evaders in Terrains Using a Chain of Seekers.
• Polishchuk, V., Arkin, E. M., Barnard, K., Coogan, K., Efrat, A., Mitchell, J. S., & Orlin, J. B. (2018). On Geometric Stable Roommates and Minimum-Weight Matching Robustness.
• Agarwal, P. K., Efrat, A., Sankararaman, S., & Zhang, W. (2017). Nearest-Neighbor Searching Under Uncertainty I. Discrete \& Computational Geometry, 58(3), 705--745.
• Ahmed, A. R., De, L. F., Devkota, S., Efrat, A., Hossain, M. I., Kobourov, S., Li, J., Salma, S. A., & Welch, E. (2017). L-Graphs and Monotone L-Graphs. arXiv preprint arXiv:1703.01544.
• Allouche, Y., Arkin, E. M., Cassuto, Y., Efrat, A., Grebla, G., Mitchell, J., Sankararaman, S., & Segal, M. (2017). Secure communication through jammers jointly optimized in geography and time. Pervasive and Mobile Computing, 41, 83--105.
• Efrat, A., Fekete, S. P., Mitchell, J. S., Polishchuk, V., & Suomela, J. (2016). Improved approximation algorithms for relay placement. ACM Transactions on Algorithms (TALG), 12(2), 20.
• Efrat, A., Fekete, S. P., Mitchell, J., Polishchuk, V., & Suomela, J. (2016). Improved Approximation Algorithms for Relay Placement. ACM Trans. Algorithms, 12(2), 20:1--20:28.
• Polishchuk, V., Arkin, E. M., Efrat, A., Knauer, C., Mitchell, J. S., Rote, G., Schlipf, L., & Talvitie, T. (2016). Shortest path to a segment and quickest visibility queries. Journal of Computational Geometry, 7(2), 77--100.
• Efrat, A., Hu, Y., Kobourov, S. G., & Pupyrev, S. (2015). MapSets: Visualizing Embedded and Clustered Graphs. J. Graph Algorithms Appl., 19(2), 571--593.
• Neumayer, S., Efrat, A., & Modiano, E. (2015). Geographic max-flow and min-cut under a circular disk failure model. Computer Networks, 77, 117--127.
• Alt, H., Arkin, E. M., Efrat, A., Hart, G., Hurtado, F., Kostitsyna, I., Kr\"oller, A., Mitchell, J. S., & Polishchuk, V. (2014). Scandinavian thins on top of cake: New and improved algorithms for stacking and packing. Theory of Computing Systems, 54(4), 689--714.
• Coutinho, M. M., Efrat, A., Johnson, T., Richa, A., & Liu, M. (2014). Healthcare Supported by Data Mule Networks in Remote Communities of the Amazon Region. International Scholarly Research Notices, 2014.
• Efrat, A., & Barnard, K. (2014). MobiSLIC: Content-Aware Energy Saving for Educational Videos on Mobile Devices. Mobile and Ubiquitous Systems: Computing, Networking, and Services: 10th International Conference, MOBIQUITOUS 2013, Tokyo, Japan, December 2-4, 2013, Revised Selected Papers, 131, 396.
• Esther, M. (2014). Data transmission and base-station placement for optimizing the lifetime of wireless sensor networks. Ad Hoc Networks, 12.
• Johnson, T., Vergara, J., Doll, C., Kramer, M., Sundararaman, G., Rajendran, H., Efrat, A., & Hingle, M. (2014). A Mobile Food Recommendation System Based on The Traffic Light Diet. arXiv preprint arXiv:1409.0296.
• Levin, L., Efrat, A., & Segal, M. (2014). Collecting data in ad-hoc networks with reduced uncertainty. Ad Hoc Networks, 17, 71-81.
  More info

  Abstract: We consider the data gathering problem in wireless ad-hoc networks where a data mule traverses a set of sensors, each with vital information on its surrounding, and collects their data. The mule goal is to collect as much information as possible thereby reducing the information uncertainty but in the same time avoid visiting some of the nodes to minimize its travel distance. We study the problem when the mule travels over a tree or a tour and propose a 3-approximation algorithm that minimizes both the information uncertainty and travel distance. We also show the applicability of our approach for solving data collection problems in varying domains such as temperature monitoring, surveillance systems and sensor placement. Simulation results show that the proposed solution converges to the optimal for varying set of topologies, such as grids, stars, linear and random networks. © 2014 Elsevier B.V. All rights reserved.
• Liron, L. (2014). Collecting data in ad-hoc networks with reduced uncertainty. Ad Hoc Networks, 17, 71--81.
• Sankararaman, S., Efrat, A., Ramasubramanian, S., & Agarwal, P. K. (2014). On channel-discontinuity-constraint routing in wireless networks. Ad hoc networks, 13, 153--169.
• Sankararaman, S., Sankararaman, S., Abu-Affash, K., Abu-Affash, K., Efrat, A., Efrat, A., Eriksson-Bique, S. D., Eriksson-Bique, S. D., Polishchuk, V., Polishchuk, V., Ramasubramanian, S., Ramasubramanian, S., Segal, M., & Segal, M. (2014). Optimization schemes for protective jamming. Mobile Networks and Applications, 19(1), 45--60.
• Suh, Y., Moon, B., Efrat, A., Kim, J., & Lee, S. (2014). Memory efficient and scalable address mapping for flash storage devices. Journal of Systems Architecture, 60(4), 357-371.
  More info

  Abstract: Flash memory devices commonly rely upon traditional address mapping schemes such as page mapping, block mapping or a hybrid of the two. Page mapping is more flexible than block or hybrid mapping without being restricted by block boundaries. However, its mapping table tends to grow large quickly as the capacity of flash memory devices does. To overcome this limitation, we propose novel mapping schemes that are fundamentally different from the existing mapping strategies. We call these new schemes Virtual Extent Trie (VET) and Extent Mapping Tree (EMT), as they manage mapping information by treating each I/O request as an extent and by using extents as basic mapping units rather than pages or blocks. By storing extents instead of individual addresses, our extent mapping schemes consume much less memory to store mapping information and still remain as flexible as page mapping. We observed in our experiments that our schemes reduced memory consumption by up to an order of magnitude in comparison with the traditional mapping schemes for several real world workloads. Our extent mapping schemes also scaled well with increasing address spaces by synthetic workloads. Even though the asymptotic mapping cost of VET and EMT is higher than the O(1) time of a page mapping scheme, the amount of increased overhead was almost negligible or low enough to be hidden by an accompanying I/O operation. © 2014 Elsevier B.V. All rights reserved.
• Agarwal, P. K., Efrat, A., Ganjugunte, S. K., Hay, D., Sankararaman, S., & Zussman, G. (2013). The resilience of WDM networks to probabilistic geographical failures. IEEE/ACM Transactions on Networking, 21(5), 1525-1538.
  More info

  Abstract: Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures in their physical infrastructure, resulting from physical attacks (such as an electromagnetic pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network, but their effects cannot be determined exactly in advance. Therefore, we provide a unified framework to model network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, when network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows to identify locations that require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience. © 1993-2012 IEEE.
• Agarwal, P. K., Efrat, A., Ganjugunte, S. K., Hay, D., Sankararaman, S., & Zussman, G. (2013). The resilience of WDM networks to probabilistic geographical failures. Networking, IEEE/ACM Transactions on, 21, 1525--1538.
• Alt, H., Arkin, E. M., Efrat, A., Hart, G., Hurtado, F., Kostitsyna, I., Kröller, A., Mitchell, J. S., & Polishchuk, V. (2013). Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing. Theory of Computing Systems, 1-26.
  More info

  Abstract: We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves. We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. We also give efficient algorithms to find the smallest rectangle simultaneously enclosing a given pair of convex polygons. © 2013 Springer Science+Business Media New York.
• Efrat, A., Amir, A., Barnard, K., & Fan, Q. (2013). Cross-modality Indexing, Browsing and Search of Distance Learning Media on the Web. Internet Multimedia Search and Mining, 353.
• Efrat, A., Nikkilä, M., & Polishchuk, V. (2013). Sweeping a terrain by collaborative aerial vehicles. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 4-13.
  More info

  Abstract: Mountainous regions are typically hard to access by land; because of this, search operations in hilly terrains are often performed by airborne force such as Unmanned Aerial Vehicles (UAVs). We give algorithms for motion planning and coordination for a team of UAVs under various assumptions on the vehicles equipage/capabilities and present outputs of an implementation of the algorithms. © 2013 ACM.
• Levin, L., Efrat, A., & Segal, M. (2013). Collecting data in ad-hoc networks with reduced uncertainty. 2013 11th International Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, WiOpt 2013, 659-666.
  More info

  Abstract: We consider the data gathering problem in wireless ad-hoc networks where a data mule traverses a set of sensors, each with vital information on its surrounding, and collects their data. The mule goal is to collect as much data as possible, thereby reducing the information uncertainty, while minimizing its travel distance. We show that the problem is solvable by a generalized version of the Prize Collecting Steiner Tree Problem, and present a dual-primal 6-approximation algorithm for solving it. Simulation results show that the proposed schema converges to the optimal results for varying set of topologies, such as grids, stars, linear and random networks. © 2013 IFIP.
• Agarwal, P. K., Efrat, A., Sankararaman, S., & Zhang, W. (2012). Nearest-neighbor searching under uncertainty. Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 225-236.
  More info

  Abstract: Nearest-neighbor queries, which ask for returning the nearest neighbor of a query point in a set of points, are important and widely studied in many fields because of a wide range of applications. In many of these applications, such as sensor databases, location based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance, which we refer to as the expected nearest neighbor (ENN). We present methods for computing an exact ENN or an ε-approximate ENN, for a given error parameter 0 < ε < 1, under dierent distance functions. These methods build an index of near-linear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or ε-approximate ENN queries with provable performance guarantees. © 2012 ACM.
• Arkin, E. M., Efrat, A., Hart, G., Kostitsyna, I., Kröller, A., Mitchell, J. S., & Polishchuk, V. (2012). Scandinavian thins on top of cake: On the smallest one-size-fits-all box. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7288 LNCS, 16-27.
  More info

  Abstract: We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves. We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. © 2012 Springer-Verlag Berlin Heidelberg.
• Efrat, A., S., J., Sankararaman, S., & Myers, P. (2012). Efficient algorithms for pursuing moving evaders in terrains. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 33-42.
  More info

  Abstract: We propose algorithms for computing optimal trajectories of a group of flying observers (such as helicopters or UAVs) searching for a lost child in a hilly terrain. Very few assumptions are made about the speed or direction of the child's motion and whether it might (either deliberately or accidentally) try to avoid being found. This framework can also be applied to seekers searching for hostile evaders, such as smugglers/criminals, or friendly evaders, such as lost hikers. Based on the features of the area of the terrain where the pursuit takes place, and the visibility and motion characteristics of the UAVs, we show how to plan their synchronized trajectories in a way that maximizes the likelihood of a successful pursuit, while minimizing their battery or fuel usage, which may, in turn, enable a longer pursuit. Our algorithm explores useful I/O-efficient data structures and branch-cutting (search pruning) techniques to achieve further speedup by limiting the storage requirements and the total number of graph nodes searched, respectively. © 2012 ACM.
• Kharitonova, Y., Tung, Q., Danehy, A., Efrat, A., & Barnard, K. (2012). Client-side backprojection of presentation slides into educational video. MM 2012 - Proceedings of the 20th ACM International Conference on Multimedia, 1005-1008.
  More info

  Abstract: A significant part of many videos of lectures is presentation slides that occupy much of the field of view. Further, for a student studying the lecture, having the slides sharply displayed is especially important, compared with the speaker, background, and audience. However, even if the original capture supports it, the bandwidth required for real time viewing is substantive, especially in the context of mobile devices. Here we propose reconstructing the video on the client side by backprojecting high resolution slide images into the video stream with the slide area blacked out. The high resolution slide deck can be sent once, and inserted into the video on the client side based on the transformation (a homography) computed in advance. We further introduce the idea that needed homography transformations can be approximated using affine transformations, which allows it to be done using built-in capabilities of HTML 5. We find that it is possible to significantly reduce bandwidth by compressing the modified video, while improving the slide area quality, but leaving the non-slide area roughly the same. © 2012 ACM.
• Neumayer, S., Efrat, A., & Modiano, E. (2012). Geographic max-flow and min-cut under a circular disk failure model. Proceedings - IEEE INFOCOM, 2736-2740.
  More info

  Abstract: Failures in fiber-optic networks may be caused by natural disasters, such as floods or earthquakes, as well as other events, such as an Electromagnetic Pulse (EMP) attack. These events occur in specific geographical locations, therefore the geography of the network determines the effect of failure events on the network's connectivity and capacity. In this paper we consider a generalization of the min-cut and max-flow problems under a geographic failure model. Specifically, we consider the problem of finding the minimum number of failures, modeled as circular disks, to disconnect a pair of nodes and the maximum number of failure disjoint paths between pairs of nodes. This model applies to the scenario where an adversary is attacking the network multiple times with intention to reduce its connectivity. We present a polynomial time algorithm to solve the geographic min-cut problem and develop an ILP formulation, an exact algorithm, and a heuristic algorithm for the geographic max-flow problem. © 2012 IEEE.
• Suh, Y., Moon, B., Efrat, A., Kim, J., & Lee, S. (2012). Extent mapping scheme for flash memory devices. Proceedings of the 2012 IEEE 20th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS 2012, 331-338.
  More info

  Abstract: Flash memory devices commonly rely on traditional address mapping schemes such as page mapping, block mapping or a hybrid of the two. Page mapping is more flexible than block mapping or hybrid mapping without being restricted by block boundaries. However, its mapping table tends to grow large quickly as the capacity of flash memory devices does. To overcome this limitation, we propose a novel mapping scheme that is fundamentally different from the existing mapping strategies. We call this new scheme Virtual Extent Trie (VET), as it manages mapping information by treating each I/O request as an extent and by using extents as basic mapping units rather than pages or blocks. By storing extents instead of individual addresses, VET consumes much less memory to store mapping information and still remains as flexible as page mapping. We observed in our experiments that VET reduced memory consumption by up to an order of magnitude in comparison with the traditional mapping schemes for several real world workloads. The VET scheme also scaled well with increasing address spaces by synthetic workloads. With a binary search mechanism, VET limits the mapping time to O(log log|U |), where U denotes the set of all possible logical addresses. Though the asymptotic mapping cost of VET is higher than the O(1) time of a page mapping scheme, the amount of increased overhead was almost negligible or low enough to be hidden by an accompanying I/O operation. © 2012 IEEE.
• Agarwal, P. K., Efrat, A., Ganjugunte, S., Hay, D., Sankararaman, S., & Zussman, G. (2011). The resilience of WDM networks to probabilistic geographical failures. Proceedings - IEEE INFOCOM, 1521-1529.
  More info

  Abstract: Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures of their physical infrastructure, resulting from physical attacks (such as an Electromagnetic Pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network but their effects are not deterministic. Therefore, we provide a unified framework to model the network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, in which network components consist of several dependent subcomponents, and in which either a 1+1 or a 1:1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, thereby demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows for identifying locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience. © 2011 IEEE.
• Agarwal, P. K., Efrat, A., Gniady, C., S., J., Polishchuk, V., & Sabhnani, G. R. (2011). Distributed localization and clustering using data correlation and the Occam's razor principle. 2011 International Conference on Distributed Computing in Sensor Systems and Workshops, DCOSS'11.
  More info

  Abstract: We present a distributed algorithm for computing a combined solution to three problems in sensor networks: localization, clustering, and sensor suspension. Assuming that initially only a rough approximation of the sensor positions is known, we show how one can use sensor measurements to refine the set of possible sensor locations, to group the sensors into clusters with linearly correlated measurements, and to decide which sensors may suspend transmission without jeopardizing the consistency of the collected data. Our algorithm applies the "Occam's razor principle" by computing a "simplest" explanation for the data gathered from the network. We also present centralized algorithms, as well as efficient heuristics. © 2011 IEEE.
• Coutinho, M. M., Moreira, T., Silva, E., Efrat, A., & Johnson, T. (2011). Work in progress: A new proposal of data mule network focused on Amazon riverine population. ACM International Conference Proceeding Series.
  More info

  Abstract: This paper presents a new proposal to provide electronic health care for riverine communities through Vehicular Ad Hoc Networks (VANETs), using boats as data mules. The focus of this project is based in specific scenarios without telecommunications infrastructure, like Marajó Archipelago, located in north of Brazil, at Amazon Forest. Copyright 2011 ACM.
• Fan, Q., Barnard, K., Amir, A., & Efrat, A. (2011). Robust spatiotemporal matching of electronic slides to presentation videos. IEEE Transactions on Image Processing, 20(8), 2315-2328.
  More info

  PMID: 21292597;Abstract: We describe a robust and efficient method for automatically matching and time-aligning electronic slides to videos of corresponding presentations. Matching electronic slides to videos provides new methods for indexing, searching, and browsing videos in distance-learning applications. However, robust automatic matching is challenging due to varied frame composition, slide distortion, camera movement, low-quality video capture, and arbitrary slides sequence. Our fully automatic approach combines image-based matching of slide to video frames with a temporal model for slide changes and camera events. To address these challenges, we begin by extracting scale-invariant feature-transformation (SIFT) keypoints from both slides and video frames, and matching them subject to a consistent projective transformation (homography) by using random sample consensus (RANSAC). We use the initial set of matches to construct a background model and a binary classifier for separating video frames showing slides from those without. We then introduce a new matching scheme for exploiting less distinctive SIFT keypoints that enables us to tackle more difficult images. Finally, we improve upon the matching based on visual information by using estimated matching probabilities as part of a hidden Markov model (HMM) that integrates temporal information and detected camera operations. Detailed quantitative experiments characterize each part of our approach and demonstrate an average accuracy of over 95% in 13 presentation videos. © 2011 IEEE.
• Tung, Q., Swaminathan, R., Efrat, A., & Barnard, K. (2011). Expanding the point-automatic enlargement of presentation video elements. MM'11 - Proceedings of the 2011 ACM Multimedia Conference and Co-Located Workshops, 961-964.
  More info

  Abstract: We present a system that assists users in viewing videos of lectures on small screen devices, such as cell phones. It automatically identifies semantic units on the slides, such as bullets, groups of bullets, and images. As the participant views the lecture, the system magnifies the appropriate semantic unit while it is the focus of the discussion. The system makes this decision based on cues from laser pointer gestures and spoken words that are read off the slide. It then magnifies the semantic element using the slide image and the homography between the slide image and the video frame. Experiments suggest that the semantic units of laser-based events identified by our algorithm closely match those identified by humans. In the case of identifying bullets through spoken words, results are more limited but are a good starting point for more complex methods. Finally, we show that this kind of magnification has potential for improving learning of technical content from video lectures when the resolution of the video is limited, such as when being viewed on hand held devices. Copyright 2011 ACM.
• Agarwal, P. K., Efrat, A., Ganjugunte, S. K., Hay, D., Sankararaman, S., & Zussman, G. (2010). Network vulnerability to single, multiple, and probabilistic physical attacks. Proceedings - IEEE Military Communications Conference MILCOM, 1824-1829.
  More info

  Abstract: Telecommunications networks heavily rely on the physical infrastructure and, are therefore, vulnerable to natural disasters, such as earthquakes or floods, as well as to physical attacks, such as an Electromagnetic Pulse (EMP) attack. Largescale disasters are likely to destroy network equipment and to severely affect interdependent systems such as the power-grid. In turn, long-term outage of the power-grid might cause additional failures to the telecommunication network. In this paper, we model an attack as a disk around its epicenter, and provide efficient algorithms to find vulnerable points within the network, under various metrics. In addition, we consider the case in which multiple disasters happen simultaneously and provide an approximation algorithm to find the points which cause the most significant destruction. Finally, since a network element does not always fail, even when it is close to the attack's epicenter, we consider a simple probabilistic model in which the probability of a network element failure is given. Under this model, we tackle the cases of single and multiple attacks and develop algorithms that identify potential points where an attack is likely to cause a significant damage. ©2010 IEEE.
• Agarwal, P. K., Efrat, A., Sharathkumar, R., & Hai, Y. u. (2010). On approximate geodesic-distance queries amid deforming point clouds. Springer Tracts in Advanced Robotics, 57, 351-365.
  More info

  Abstract: We propose data structures for answering a geodesic-distance query between two query points in a two-dimensional or three-dimensional dynamic environment, in which obstacles are deforming continuously. Each obstacle in the environment is modeled as the convex hull of a continuously deforming point cloud. The key to our approach is to avoid maintaining the convex hull of each point cloud explicitly but still able to retain sufficient geometric information to estimate geodesic distances in the free space. © 2009 Springer-Verlag.
• Arango, J., Efrat, A., Ramasubramanian, S., Pink, S., & Krunz, M. (2010). Retransmission and backoff strategies for wireless broadcasting. Ad Hoc Networks, 8(1), 77--95.
• Efrat, A., Forrester, D., Iyer, A., Kobourov, S. G., Erten, C., & Kilic, O. (2010). Force-directed approaches to sensor localization. ACM Transactions on Sensor Networks (TOSN), 7(3), 27.
• Efrat, A., Forrester, D., Iyer, A., Kobourov, S. G., Erten, C., & Kilic, O. (2010). Force-directed approaches to sensor localization. ACM Transactions on Sensor Networks, 7(3).
  More info

  Abstract: As the number of applications of sensor networks increases, so does the interest in sensor network localization, that is, in recovering the correct position of each node in a network of sensors from partial connectivity information such as adjacency, range, or angle between neighboring nodes. In this article, we consider the anchor-free localization problem in sensor networks that report possibly noisy range information and angular information about the relative order of each sensor's neighbors. Previously proposed techniques seem to successfully reconstruct the original positions of the nodes for relatively small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with nonconvex or nonsimple underlying topology. Moreover, the distributed nature of the problem makes some of the centralized techniques inapplicable in distributed settings. To address these problems we describe a multiscale dead-reckoning (MSDR) algorithm that scales well for large networks, can reconstruct complex underlying topologies, and is resilient to noise. The MSDR algorithm takes its roots from classic force-directed graph layout computation techniques. These techniques are augmented with a multiscale extension to handle the scalability issue and with a dead-reckoning extension to overcome the problems arising with nonsimple topologies. Furthermore, we show that the distributed version of the MSDR algorithm performs as well as, if not better than, its centralized counterpart, as shown by the quality of the layout, measured in terms of the accuracy of the computed pairwise distances between sensors in the network. © 2010 ACM 1550-4859/2010/09-ART20.
• Swaminathan, R., Thompson, M. E., Fong, S., Efrat, A., Amir, A., & Barnard, K. (2010). Improving and aligning speech with presentation slides. Proceedings - International Conference on Pattern Recognition, 3280-3283.
  More info

  Abstract: We present a novel method to correct automatically generated speech transcripts of talks and lecture videos using text from accompanying presentation slides. The approach finesses the challenges of dealing with technical terms which are often outside the vocabulary of speech recognizers. Further, we align the transcript to the slide word sequence so that we can improve the organization of closed captioning for hearing impaired users, and improve automatic highlighting or magnification for visually impaired users. For each speech segment associated with a slide, we construct a sequential Hidden Markov Model for the observed phonemes that follows slide word order, interspersed with text not on the slide. Incongruence between slide words and mistaken transcript words is accounted for using phoneme confusion probabilities. Hence, transcript words different from aligned high probability slide words can be corrected. Experiments on six talks show improvement in transcript accuracy and alignment with slide words. © 2010 IEEE.
• Arkin, E. M., Arkin, E. M., Bae, S. W., Bae, S. W., Efrat, A., Efrat, A., Okamoto, K., Okamoto, K., Mitchell, J. S., Mitchell, J. S., Polishchuk, V., & Polishchuk, V. (2009). Geometric stable roommates. Information Processing Letters, 109(4), 219-224.
  More info

  Abstract: 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 given by the sorted list of distances to the other participants. We show that contrary to the general case, the problem admits a polynomial-time solution even in the case when ties are present in the preference lists. We define the notion of an α-stable matching: the participants are willing to switch partners only for a (multiplicative) improvement of at least α. We prove that, in general, finding α-stable matchings is not easier than finding matchings that are stable in the usual sense. We show that, unlike in the general case, in a three-dimensional geometric stable roommates problem, a 2-stable matching can be found in polynomial time. © 2008 Elsevier B.V. All rights reserved.
• Fan, Q., Barnard, K., Amir, A., & Efrat, A. (2009). Accurate alignment of presentation slides with educational video. Proceedings - 2009 IEEE International Conference on Multimedia and Expo, ICME 2009, 1198-1201.
  More info

  Abstract: Spatio-temporal alignment of electronic slides with corresponding presentation video opens up a number of possibilities for making the instructional content more accessible and understandable, such as video quality improvement, better content analysis and novel compression approaches for low bandwidth access. However, these applications need finding accurate transformations between slides and video frames, which is quite challenging in capture settings using pan-tiltzoom (PTZ) cameras. In this paper we present a nonlinear optimization approach for accurate registration of slide images to video frames. Instead of estimating the projective transformation (i.e., homography) between a single pair of slide and frame images, we solve a set of homographies jointly in a frame sequence that is associated with a given slide. Quantitative evaluation confirms that this substantively improves alignment accuracy. ©2009 IEEE.
• Sankararaman, S., Efrat, A., Ramasubramanian, S., & Taheri, J. (2009). Scheduling sensors for guaranteed sparse coverage. arXiv preprint arXiv:0911.4332.
• Shi, Y., Hou, Y. T., & Efrat, A. (2009). Algorithm design for a class of base station location problems in sensor networks. Wireless Networks, 15(1), 21-38.
  More info

  Abstract: Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1- ε) approximation algorithms for base station placement problems under any desired small error bound ε > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1/ε2 complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem when the optimization objective is to maximize network capacity. Our (1- ε) approximation algorithm is the first theoretical result on this problem. © 2007 Springer Science+Business Media, LLC.
• Winslow, A., Tung, Q., Fan, Q., Torkkola, J., Swaminathan, R., Barnard, K., Amir, A., Efrat, A., & Gniady, C. (2009). Studying on the move - Enriched presentation video for mobile devices. Proceedings - IEEE INFOCOM.
  More info

  Abstract: The rapid adoption of distance learning means that significant lecture video content is available on-line. However, access from mobile devices is hampered by low bandwidth and small screen size. In this paper, we address these issues by manipulating two key elements of lecture video-displayed slides and laser pointer gestures. Displayed slides need to be very crisp compared to background content. Fortunately, the needed data is available from the presentation slides, and we describe a method for splicing them into the video on the client side, increasing fidelity, and reducing bandwidth needs. This operation removes laser pointer gestures, which are often lost due to compression, and are hard to see on the small screens of mobile regardless. But these gestures are part of what makes watching lecture video different than simply looking at the slides. Hence we interpret the laser pointer gestures as we analyze the videos, creating representations that can be transmitted at a low cost. These representations can then be iconified on the client side and displayed clearly.
• Efrat, A. (2008). Guest editor's foreword. International Journal of Computational Geometry and Applications, 18(1-2), 1-2.
• Efrat, A., Fekete, S. P., Gaddehosur, P. R., S., J., Polishchuk, V., & Suomela, J. (2008). Improved approximation algorithms for relay placement. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5193 LNCS, 356-367.
  More info

  Abstract: In the relay placement problem the input is a set of sensors and a number r ≥ 1, the communication range of a relay. The objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. We present a 3.11-approximation algorithm, and show that the problem admits no PTAS, assuming P ≠ NP. © 2008 Springer-Verlag Berlin Heidelberg.
• Ezra, E., Sharir, M., & Efrat, A. (2008). On the performance of the ICP algorithm. Computational Geometry: Theory and Applications, 41(1-2), 77-93.
  More info

  Abstract: We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay as a successful heuristic for matching of point sets in d-space under translation, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, under the RMS measure, for which we present a lower bound construction of Ω(nlogn) iterations, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case. We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not. © 2008 Elsevier B.V.
• Ezra, E., Sharir, M., & Efrat, A. (2008). On the performance of the ICP algorithm. Computational Geometry, 41(1-2), 77--93.
• Amir, A., Efrat, A., Myllymaki, J., Palaniappan, L., & Wampler, K. (2007). Buddy tracking - efficient proximity detection among mobile friends. Pervasive and Mobile Computing, 3(5), 489-511.
  More info

  Abstract: Global positioning systems (GPS) and mobile phone networks make it possible to track individual users with an increasing accuracy. It is natural to ask whether this information can be used to maintain social networks. In such a network each user wishes to be informed whenever one of a list of other users, called the user's friends, appears in the user's vicinity. In contrast to more traditional positioning based algorithms, the computation here depends not only on the user's own position on a static map, but also on the dynamic position of the user's friends. Hence it requires both communication and computation resources. The computation can be carried out either between the individual users in a peer-to-peer fashion or by centralized servers where computation and data can be collected at one central location. In the peer-to-peer model, a novel algorithm for minimizing the number of location update messages between pairs of friends is presented. We also present an efficient algorithm for the centralized model, based on region hierarchy and quadtrees. The paper provides an analysis of the two algorithms, compares them with a naive approach, and evaluates them on user motions generated by the IBM City Simulator system. © 2007 Elsevier Ltd. All rights reserved.
• Amir, A., Efrat, A., Myllymaki, J., Palaniappan, L., & Wampler, K. (2007). Buddy tracking—efficient proximity detection among mobile friends. Pervasive and Mobile Computing, 3(5), 489--511.
• Brass, P., Cenek, E., Duncan, C. A., Efrat, A., Erten, C., Ismailescu, D. P., Kobourov, S. G., Lubiw, A., & Mitchell, J. S. (2007). On simultaneous planar graph embeddings. Computational Geometry: Theory and Applications, 36(2), 117-130.
  More info

  Abstract: We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another in which the mapping is not given. We present positive and negative results for the two versions of the problem. Among the positive results with given mapping, we show that we can embed two paths on an n×n grid, and two caterpillar graphs on a 3n×3n grid. Among the negative results with given mapping, we show that it is not always possible to simultaneously embed three paths or two general planar graphs. If the mapping is not given, we show that any number of outerplanar graphs can be embedded simultaneously on an O(n)×O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O( n2)×O( n2) grid. © 2006 Elsevier B.V. All rights reserved.
• Brass, P., Cenek, E., Duncan, C. A., Efrat, A., Erten, C., Ismailescu, D. P., Kobourov, S. G., Lubiw, A., & Mitchell, J. S. (2007). On simultaneous planar graph embeddings. Computational Geometry, 36(2), 117--130.
• Cheong, O., Efrat, A., & Har-Peled, S. (2007). Finding a guard that sees most and a shop that sells most. Discrete \& Computational Geometry, 37(4), 545--563.
• Cheong, O., Efrat, A., & Har-Peled, S. (2007). Finding a guard that sees most and a shop that sells most. Discrete and Computational Geometry, 37(4), 545-563.
  More info

  Abstract: 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 for finding the point that will have approximately the largest Voronoi region when added to an n-point set in the plane. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time, and the rigid motion doing so in near-cubic time. © Springer 2007.
• Efrat, A., Erten, C., & Kobourov, S. G. (2007). Fixed-Location Circular Arc Drawing of Planar Graphs.. J. Graph Algorithms Appl., 11(1), 145--164.
• Efrat, A., Erten, C., & Kobourov, S. G. (2007). Fixed-location circular arc drawing of planar graphs. Journal of Graph Algorithms and Applications, 11(1), 145-164.
  More info

  Abstract: 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 every edge we have only two possible circular arcs, then a simple reduction to 2SAT yields an O(n 2) algorithm to find out if a drawing with no crossings can be realized, where n is the number of vertices in the graph. We present an improved O(n 7/4 poly log n) time algorithm for this problem. For the special case where the possible circular arcs for each edge are of the same length, we present an even more efficient algorithm that runs in O(n 3/2 poly log n) time. We also consider two related optimization versions of the problem. First we show that minimizing the number of crossings is NP-hard. Second we show that maximizing the number of edges that can be realized without crossings is also NP-hard. Finally, we show that if we have three or more possible circular arcs per edge, deciding whether a drawing with no crossings can be realized is NP-hard.
• Efrat, A., Fan, Q., & Venkatasubramanian, S. (2007). Curve matching, time warping, and light fields: New algorithms for computing similarity between curves. Journal of Mathematical Imaging and Vision, 27(3), 203-216.
  More info

  Abstract: 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 studied extensively by computational geometers, and many measures of similarity have been examined, among them being the Fréchet distance (sometimes referred in folklore as the "dog-man" distance). A measure that is very closely related to the Fréchet distance but has never been studied in a geometric context is the Dynamic Time Warping measure (DTW), first used in the context of speech recognition. This measure is ubiquitous across different domains, a surprising fact because notions of similarity usually vary significantly depending on the application. However, this measure suffers from some drawbacks, most importantly the fact that it is defined between sequences of points rather than curves. Thus, the way in which a curve is sampled to yield such a sequence can dramatically affect the quality of the result. Some attempts have been made to generalize the DTW to continuous domains, but the resulting algorithms have exponential complexity. In this paper we propose similarity measures that attempt to capture the "spirit" of dynamic time warping while being defined over continuous domains, and present efficient algorithms for computing them. Our formulation leads to a very interesting connection with finding short paths in a combinatorial manifold defined on the input chains, and in a deeper sense relates to the way light travels in a medium of variable refractivity. © Springer Science + Business Media, LLC 2007.
• Efrat, A., Guibas, L. J., Hall-Holt, O. A., & Zhang, L. (2007). On incremental rendering of silhouette maps of a polyhedral scene. Computational Geometry: Theory and Applications, 38(3), 129-138.
  More info

  Abstract: 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 as large as many millions. It is sometimes advantageous to render only the silhouettes of the objects, rather than the objects themselves. Such an approach is regularly used for example in the domain of non-photorealistic rendering, where the rendering of silhouette edges plays a key role. The difficult part in efficiently implementing a kinetic approach to this problem is to realize when the rendered silhouette undergoes a combinatorial change. In this paper, we obtain bounds on several problems involving the number of these events for a collection of k objects, with a total of n edges. We assume that our objects are convex polytopes, and that the viewpoint is moving along a straight line, or along an algebraic curve of bounded low degree. We also study the special case when the scene is a polyhedral terrain, and present improved bounds for this case. In addition to bounding the number events, we also obtain algorithms that compute all the changes occurring during a linear motion both for general scenes and for terrains. © 2007 Published by Elsevier B.V.
• Efrat, A., Guibas, L. J., Hall-Holt, O. A., & Zhang, L. i. (2007). On incremental rendering of silhouette maps of a polyhedral scene. Computational Geometry, 38(3), 129--138.
• Fan, Q., Amir, A., Barnard, K., Swaminathan, R., & Efrat, A. (2007). Temporal modeling of slide change in presentation videos. ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 1, I989-I992.
  More info

  Abstract: We develop a general framework to automatically match electronic slides to the videos of the corresponding presentations. The synchronized slides support indexing and browsing of educational and corporate digital video libraries. Our approach extends previous work that matches slides, based on visual features alone, and integrates multiple cues to, further improve performance in more difficult cases. We model slide change in a presentation with a dynamic Hidden Markov Model (ITMM) that captures the temporal notion of slide change and whose transition probabilities are adapted locally by using the camera events in the inference process, Our results show that, combining multiple, cues in a state model can greatly improve, the performance in ambiguous cases. © 2007 IEEE.
• Narro, M. L., Yang, F., Kraft, R., Wenk, C., Efrat, A., & Restifo, L. L. (2007). NeuronMetrics: Software for semi-automated processing of cultured neuron images. Brain Research, 1138(1), 57-75.
  More info

  PMID: 17270152;PMCID: PMC1945162;Abstract: Using primary cell culture to screen for changes in neuronal morphology requires specialized analysis software. We developed NeuronMetrics™ for semi-automated, quantitative analysis of two-dimensional (2D) images of fluorescently labeled cultured neurons. It skeletonizes the neuron image using two complementary image-processing techniques, capturing fine terminal neurites with high fidelity. An algorithm was devised to span wide gaps in the skeleton. NeuronMetrics uses a novel strategy based on geometric features called faces to extract a branch number estimate from complex arbors with numerous neurite-to-neurite contacts, without creating a precise, contact-free representation of the neurite arbor. It estimates total neurite length, branch number, primary neurite number, territory (the area of the convex polygon bounding the skeleton and cell body), and Polarity Index (a measure of neuronal polarity). These parameters provide fundamental information about the size and shape of neurite arbors, which are critical factors for neuronal function. NeuronMetrics streamlines optional manual tasks such as removing noise, isolating the largest primary neurite, and correcting length for self-fasciculating neurites. Numeric data are output in a single text file, readily imported into other applications for further analysis. Written as modules for ImageJ, NeuronMetrics provides practical analysis tools that are easy to use and support batch processing. Depending on the need for manual intervention, processing time for a batch of ∼ 60 2D images is 1.0-2.5 h, from a folder of images to a table of numeric data. NeuronMetrics' output accelerates the quantitative detection of mutations and chemical compounds that alter neurite morphology in vitro, and will contribute to the use of cultured neurons for drug discovery. © 2006 Elsevier B.V. All rights reserved.
• Narro, M. L., Yang, F., Kraft, R., Wenk, C., Efrat, A., & Restifo, L. L. (2007). NeuronMetrics: software for semi-automated processing of cultured neuron images. Brain research, 1138, 57--75.
• Aronov, B., Efrat, A., Koltun, V., & Sharir, M. (2006). On the union of $\kappa$-round objects in three and four dimensions. Discrete \& Computational Geometry, 36(4), 511--526.
• Aronov, B., Efrat, A., Koltun, V., & Sharir, M. (2006). On the union of κ-round objects in three and four dimensions. Discrete and Computational Geometry, 36(4), 511-526.
  More info

  Abstract: A compact set c in ℝ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 combinatorial complexity of the union of n κ-round, not necessarily convex, objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n 3+ε)) for any ε > 0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight in the worst case. © Springer 2006.
• Barnard, K., Connolly, A., Denneau, L., Efrat, A., Grav, T., Heasley, J., Jedicke, R., Kubica, J., Moon, B., Morris, S. H., & Rao, P. R. (2006). The LSST moving object processing pipeline. Proceedings of SPIE - The International Society for Optical Engineering, 6270.
  More info

  Abstract: We describe a proposed architecture for the Large Synoptic Survey Telescope (LSST) moving object processing pipeline based on a similar system under development for the Pan-STARRS project. This pipeline is responsible for identifying and discovering fast moving objects such as asteroids, updating information about them, generating appropriate alerts, and supporting queries about moving objects. Of particular interest are potentially hazardous asteroids (PHA's). We consider the system as being composed of two interacting components. First, candidate linkages corresponding to moving objects are found by tracking detections ("tracklets"). To achieve this in reasonable time we have developed specialized data structures and algorithms that efficiently evaluate the possibilities using quadratic fits of the detections on a modest time scale. For the second component we take a Bayesian approach to validating, refining, and merging linkages over time. Thus new detections increase our belief that an orbit is correct and contribute to better orbital parameters. Conversely, missed expected detections reduce the probability that the orbit exists. Finally, new candidate linkages are confirmed or refuted based on previous images. In order to assign new detections to existing orbits we propose bipartite graph matching to find a maximum likelihood assignment subject to the constraint that detections match at most one orbit and vice versa. We describe how to construct this matching process to properly deal with false detections and missed detections.
• CHRISTIAN, A. D., Efrat, A., KOBOUROV, S., & Wenk, C. (2006). Drawing with fat edges. International Journal of Foundations of Computer Science, 17(05), 1143--1163.
• Duncan, C. A., Efrat, A., Kobourov, S., & Wenk, C. (2006). Drawing with fat edges. International Journal of Foundations of Computer Science, 17(5), 1143-1163.
  More info

  Abstract: Traditionally, graph drawing algorithms represent vertices as circles and edges as curves connecting the vertices. We introduce the problem of drawing with "fat" edges, i.e., with edges of variable thickness. The thickness of an edge is often used as a visualization cue, to indicate importance, or to convey some additional information. We present a model for drawing with fat edges and a corresponding efficient polynomial time algorithm that uses the model. We first focus on a restricted class of graphs that occur in VLSI wire routing and then show how to extend the algorithm to general planar graphs. We show how to convert an arbitrary wire routing into a homotopically equivalent routing that maximizes the distance between any two wires, which is a desired property in VLSI design. Among such, we obtain the routing with minimum total wire length. A homotopically equivalent routing that maximizes the distance between any two wires yields a graph drawing which maximizes edge thickness. Our algorithm does not require unit edge thickness but can be applied as well in the presence of different edge weights. © World Scientific Publishing Company.
• Efrat, A., & Har-Peled, S. (2006). Guarding galleries and terrains. Information processing letters, 100(6), 238--245.
• Efrat, A., Efrat, A., Har-Peled, S., & Har-Peled, S. (2006). Guarding galleries and terrains. Information Processing Letters, 100(6), 238-245.
  More info

  Abstract: 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 algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes. © 2006 Elsevier B.V. All rights reserved.
• Efrat, A., Forrester, D., Iyer, A., Kobourov, S. G., & Erten, C. (2006). Force-directed approaches to sensor localization. Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics, 2006, 108-118.
  More info

  Abstract: 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 angular information about the relative order of each sensor's neighbors. We experimented with classic and new force-directed techniques. The classic techniques work well for small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with noisy data. We describe a new force-directed technique, based on a multi-scale dead-reckoning, that scales well for large networks, is resilient under range errors, and can reconstruct complex underlying regions.
• Efrat, A., Kobourov, S. G., & Lubiw, A. (2006). Computing homotopic shortest paths efficiently. Computational Geometry: Theory and Applications, 35(3), 162-172.
  More info

  Abstract: We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k out+k inlogn+n√n), and the randomized algorithm runs in expected time O(k out+k inlogn+n(logn) 1+ε). Here k in is the number of edges in all the paths of Π, and k out is the number of edges in the output paths. © 2006 Elsevier B.V. All rights reserved.
• Efrat, A., Kobourov, S. G., & Lubiw, A. (2006). Computing homotopic shortest paths efficiently. Computational Geometry, 35(3), 162--172.
• Ezra, E., Sharir, M., & Efrat, A. (2006). On the ICP algorithm. Proceedings of the Annual Symposium on Computational Geometry, 2006, 95-104.
  More info

  Abstract: We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay [4] as a successful heuristics for pattern matching under translation, where the input consists of two point sets in d-space, for d ≥ 1, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-directional) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, for which we present a lower bound construction of Ω(n log n) iterations under the RMS measure, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case. We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the rel ative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not. Copyright 2006 ACM.
• Fan, Q., Barnard, K., Amir, A., Efrat, A., & Lin, M. (2006). Matching slides to presentation videos using SIFT and scene background matching. Proceedings of the ACM International Multimedia Conference and Exhibition, 239-248.
  More info

  Abstract: 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 large variety of videos, various frame compositions and color balances, arbitrary slides sequence and with dynamic cameras switching, pan, tilt and zoom. To achieve high accuracy, we develop a two-phases process with unsupervised scene background modelling. In the first phase, scale invariant feature transform (SIFT) keypoints are applied to frame to slide matching, under constraint projective transformation (constraint homography) using a random sample consensus (RANSAC). Successful first-phase matches are then used to automatically build a scene background model. In the second phase the background model is applied to the remaining unmatched frames to boost the matching performance for difficult cases such as wide field of view camera shots where the slide shows as a small portion of the frame. We also show that color correction is helpful when color-related similarity measures are used for identifying slides. We provide detailed quantitative experimentation results characterizing the effect of each part of our approach. The results show that our approach is robust and achieves high performance on matching slides to a number of videos with different styles. Copyright 2006 ACM.
• Kraft, R., Escobar, M. M., Narro, M. L., Kurtis, J. L., Efrat, A., Barnard, K., & Restifo, L. L. (2006). Phenotypes of Drosophila brain neurons in primary culture reveal a role for fascin in neurite shape and trajectory. Journal of Neuroscience, 26(34), 8734-8747.
  More info

  PMID: 16928862;Abstract: 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 resolution. Gamma neurons of Drosophila melanogaster mushroom bodies (MBs) are remodeled during metamorphosis under the control of the steroid hormone 20-hydroxyecdysone (20E). In vitro, wild-type γ neurons retain characteristic morphogenetic features, notably a single axon-like dominant primary process and an arbor of short dendrite-like processes, as determined with microtubule-polarity markers. We found three distinct genetically determined phenotypes of cultured neurons from grossly normal brains, suggesting that subtle in vivo attributes are unmasked and amplified in vitro. First, the neurite outgrowth response to 20E is sexually dimorphic, being much greater in female than in male γ neurons. Second, the γ neuron-specific "naked runt" phenotype results from transgenic insertion of an MB-specific promoter. Third, the recessive, panneuronal "filagree" phenotypemapsto singed, which encodes the actin-bundling protein fascin. Fascin deficiency does not impair the 20E response, but neurites fail to maintain their normal, nearly straight trajectory, instead forming curls and hooks. This is accompanied by abnormally distributed filamentous actin. This is the first demonstration of fascin function in neuronal morphogenesis. Our findings, along with the regulation of human Fascin1 (OMIM 602689) by CREB (cAMP response element-binding protein) binding protein, suggest FSCN1 as a candidate gene for developmental brain disorders. We developed an automated method of computing neurite curvature and classifying neurons based on curvature phenotype. This will facilitate detection of genetic and pharmacological modifiers of neuronal defects resulting from fascin deficiency. Copyright © 2006 Society for Neuroscience.
• Shi, Y., Hou, Y. T., & Efrat, A. (2006). Algorithm design for base station placement problems in sensor networks. ACM International Conference Proceeding Series, 191.
  More info

  Abstract: Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1 - ) approximation algorithms for base station placement problems under any desired small error bound > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1 / 2 complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem for maximizing network capacity. Our (1 - ) approximation algorithm is the first theoretical result on this problem. © 2006 ACM.
• Suri, S., Guibas, L. J., & Efrat, A. (2006). Geometric Approaches to Ad Hoc and Sensor Networks: Full Report of the 2006 NSF Workshop.
• Efrat, A. (2005). The complexity of the union of ($\alpha$,$\beta$)-covered objects. SIAM Journal on Computing, 34(4), 775--787.
• Efrat, A. (2005). The complexity of the union of (α,β)-covered objects. SIAM Journal on Computing, 34(4), 775-787.
  More info

  Abstract: 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 at least α > 0 and all its edges are at least β.diam(c)-long. This notion extends that of fat convex objects. We show that the combinatorial complexity of the union of n (α, β)-covered objects of "constant description complexity" is O(λ s+2(n) log 2 n log log n), where s is the maximum number of intersections between the boundaries of any pair of given objects, and λ s (n) denotes the maximum length of an (n, s)-Davenport-Schinzel sequence. Our result extends and improves previous results concerning convex α-fat objects. © 2005 Society for Industrial and Applied Mathematics.
• Efrat, A., Har-Peled, S., & S., J. (2005). Approximation algorithms for two optimal location problems in sensor networks. 2nd International Conference on Broadband Networks, BROADNETS 2005, 2005, 767-776.
  More info

  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 among a set of sensors each of which has a data stream to get to the base station. Subject to power constraints at the sensors, our goal is to locate the base station and establish a network in order to maximize the lifespan of the network. Second, we study optimal sensor placement problems for quality coverage of given domains cluttered with obstacles. We assume "line-of-site", sensors, that sense a point only if the straight segment connecting the sensor to this point (the "line-of-site") does not cross any obstacle, so obstacles occludes area from Using line-of-site sensors, the goal is to minimize the number of sensors required in order to have each point "well covered" according to precise criteria (e.g., that each point is seen by two sensors that form at least angle α, or that each point is seen by three sensors that form a triangle containing the point). © 2005 IEEE.
• Fan, Q., Efrat, A., Koltun, V., Krishnan, S., & Venkatasubramanian, S. (2005). Hardware-assisted natural neighbor interpolation. Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics, 111-120.
  More info

  Abstract: Natural neighbor interpolation is a weighted average interpolation method that is based on Voronoi tessellation. In this paper, we present and implement an algorithm for performing natural neighbor interpolation using graphics hardware. Unlike traditional software-based approaches that process one query at a time, we develop a scheme that computes the entire scalar field induced by natural neighbor interpolation, at which point a query is a trivial array lookup, arid range queries over the field are easy to perform. Our approach is faster than the best known software implementations and makes use of general purpose stream programming capabilities of current graphics cards. We also present a simple scheme that requires no advanced graphics capabilities and can process natural neighbor queries faster than existing software-based approaches. Finally, recognizing the limitation incurred by the bounded size of graphics frame buffers, we propose a sub-division approach that allows performing queries locally in a subdivision of the input domain. This approach can reduce to a negligibly small degree (< 1%) the loss of precision caused by the naive scaling method while still processing queries faster than the software-based approaches when the number of sites is large.
• Kubica, J., Axelrod, T., Barnard, K., Connolly, A., Denneau, L., Efrat, A., Heasley, J., Jedicke, R., Moon, B., Moore, A., & others, . (2005). Efficiently Tracking Moving Sources in the LSST. Bulletin of the American Astronomical Society, 37, 4.
• Shi, Y. i., Hou, Y. T., & Efrat, A. (2005). Design of low-complexity approximation algorithms for base station placement problems in sensor networks. Technical Report-Bradley Dept. of ECE Virginia Tech.
• Amir, A., Efrat, A., Myllymaki, J., Palaniappan, L., & Wampler, K. (2004). Buddy tracking - Efficient proximity detection among mobile friends. Proceedings - IEEE INFOCOM, 1, 298-309.
  More info

  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 one can use this information to maintain social networks. Here each user wishes to be informed whenever one of a list of other users, called the user's friends, appears in the user's vicinity. In contrast to more traditional positioning based algorithms, the computation here depends not only on the user's own position on a static map, but also on the dynamic position of the user's friends. Hence it requires both communication and computation resources. The computation can be carried out either between the individual users in a peer-to-peer fashion or by centralized servers where computation and data can be collected at one central location. In the peer-to-peer model, a novel algorithm for minimizing the number of location update messages between pairs of friends is presented. We also present an efficient algorithm for the centralized model, based on region hierarchy and quadtrees. The paper provides an analysis of the two algorithms, compares them with a naive approach, and evaluates them using the IBM City Simulator system.
• Aronov, B., Efrat, A., Koltun, V., & Sharir, M. (2004). On the union of κ-round objects in three and four dimensions. Proceedings of the Annual Symposium on Computational Geometry, 383-390.
  More info

  Abstract: A compact body c in ℝ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 combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n 3+ε)) for any ε > 0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.
• Cheong, O., Efrat, A., & Har-Peled, S. (2004). On Finding a Guard that Sees Most and a Shop that Sells Most. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 15, 1091-1100.
  More info

  Abstract: 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 finding the point that will have approximately the largest Voronoi region when added to an n-point set. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time.
• Efrat, A., Erten, C., & Kobourov, S. G. (2004). Fixed-Location Circular-Arc Drawing of Planar Graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2912, 147-158.
  More info

  Abstract: 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 is the number of vertices in the graph. If for every edge we have only two possible circular arcs, then a simple reduction to 2SAT yields an O(n 2) algorithm to find out if a drawing with no crossings can be realized. We present an improved O(n 7/4 polylog n) time algorithm. For the special case where the possible circular arcs for each edge are of the same length, we present an even more efficient algorithm that runs in O(n 3/2 polylog n) time. We also consider the problem if we have more than two possible circular arcs per edge and show that the problem becomes NP-Hard. Moreover, we show that two optimization versions of the problem are also NP-Hard. © Springer-Verlag 2004.
• Efrat, A., Hoffmann, F., Knauer, C., Kriegel, K., Rote, G., & Wenk, C. (2004). Covering with ellipses. Algorithmica, 38(1), 145--160.
• Efrat, A., Indyk, P., & Venkatasubramanian, S. (2004). Pattern matching for sets of segments. Algorithmica (New York), 40(3), 147-160.
  More info

  Abstract: 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 naturally from problems in mapping buildings and robot exploration. We propose a new criterion for segment similarity called the coverage measure, and present efficient algorithms for maximizing it between sets of axis-parallel segments under translations. In the general case, we present a procedure running in time O(n3 log 2 n), and for the case when all segments are horizontal, we give a procedure that runs in time O(n2 log2 n). Here n is the number of segments. In addition, we show that an ε-approximation to the Hausdorff distance between two sets of horizontal segments under vertical translations can be computed in time O(n3/2 max(poly(log M, log n, 1/ε))). Here, M denotes the ratio of the diameter to the closest pair of points in the sets of segments (where pairs of points lie on different segments). These algorithms are significant improvements over the general algorithm of Agarwal et al. that required time O(n4 log2. © 2004 Springer-Verlag New York, LLC.
• Alt, H., Efrat, A., Rote, G., & Wenk, C. (2003). Matching planar maps. Journal of Algorithms, 49(2), 262-283.
  More info

  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 systems, etc. More precisely, we define feasible distance measures that reflect how close a given pattern H is to some part of a larger pattern G. These distance measures are generalizations of the well-known Fréchet distance for curves. We first give an efficient algorithm for the case that H is a polygonal curve and G is a geometric graph. Then, slightly relaxing the definition of distance measure, we give an algorithm for the general case where both, H and G, are geometric graphs. © 2003 Elsevier Inc. All rights reserved.
• Alt, H., Efrat, A., Rote, G., & Wenk, C. (2003). Matching planar maps. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 589-598.
  More info

  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 systems, etc. More precisely, we will define feasible distance measures that reflect how close a given pattern H is to some part of a larger pattern G. These distance measures are generalizations of the well known Fréchet distance for curves. We will first give an efficient algorithm for the case that H is a polygonal curve and G is a geometric graph. Then, slightly relaxing the definition of distance measure we will give an algorithm for the general case where both, H and G, are geometric graphs.
• Amir, A., Srinivasan, S., & Efrat, A. (2003). Search the audio, browse the video - A generic paradigm for video collections. Eurasip Journal on Applied Signal Processing, 2003(2), 209-222.
  More info

  Abstract: 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, retrieval, and browsing technology. Most prior work in the field can be roughly categorized into two classes. One class is based on image processing techniques, often called content-based image and video retrieval, in which video frames are indexed and searched for visual content. The other class is based on spoken document retrieval, which relies on automatic speech recognition and text queries. Both approaches have major limitations. In the first approach, semantic queries pose a great challenge, while the second, speech-based approach, does not support efficient video browsing. This paper describes a system where speech is used for efficient searching and visual data for efficient browsing, a combination that takes advantage of both approaches. A fully automatic indexing and retrieval system has been developed and tested. Automated speech recognition and phonetic speech indexing support text-to-speech queries. New browsable views are generated from the original video. A special synchronized browser allows instantaneous, context-preserving switching from one view to another. The system was successfully used to produce searchable-browsable video proceedings for three local conferences.
• Brass, P., Cenek, E., Duncan, C. A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S. G., Lubiw, A., & Mitchell, J. S. (2003). On simultaneous planar graph embeddings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2748, 243-255.
  More info

  Abstract: We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another in which the mapping is not given. In particular, given a mapping, we show how to embed two paths on an n x n grid, and two caterpillar graphs on a 3n x 3n grid. We show that it is not always possible to simultaneously embed three paths. If the mapping is not given, we show that any number of outerplanar graphs can be embedded simultaneously on an O(n) x O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n 2) x O(n 2) grid. © Springer-Verlag Berlin Heidelberg 2003.
• Dror, M., Lubiw, A., Efrat, A., & Mitchell, J. S. (2003). Touring a sequence of polygons. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 473-482.
  More info

  Abstract: 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(nk2 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(n2 log n) time and the watchman route problem (through a fixed point s) in time O(n3 log n), compared with the previous time bounds of O(n3) and O(n4), respectively.
• Efrat, A., González-Baños, H. H., Kobourov, S. G., & Palaniappan, L. (2003). Optimal strategies to track and capture a predictable target. Proceedings - IEEE International Conference on Robotics and Automation, 3, 3789-3796.
  More info

  Abstract: We present an O(n log1+ε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.
• Efrat, A., Hoffmann, F., Knauer, C., Kriegel, K., Rote, G., & Wenk, C. (2003). Covering with ellipses. Algorithmica (New York), 38(1), 145-160.
  More info

  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 such covers and present an efficient randomized approximation algorithm for the cover construction. This question is motivated by a special pattern recognition task where one has to identify ellipse-shaped protein spots in two-dimensional electrophoresis images. © 2003 Springer-Verlag New York Inc.
• Wenk, C., Alt, H., Efrat, A., Palaniappan, L., & Rote, G. (2003). Finding a curve in a map. Proceedings of the Annual Symposium on Computational Geometry, 384-385.
  More info

  Abstract: An efficient algorithm to find a path in the graph, which is most similar to the polygonal curve provided as input, was discussed. The algorithm is based upon the well-known Frechet distance for curves. The algorithm was implemented in C with a graphical user interface using OpenGL.
• Duncan, C. A., Efrat, A., Kobourov, S. G., & Wenk, C. (2002). Drawing with fat edges. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2265 LNCS, 162-177.
  More info

  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 vertices. In this paper we consider the problem of drawing graphs with edges of variable thickness. The thickness of an edge is often used as a visualization cue, to indicate importance, or to convey some additional information. We present a model for drawing with fat edges and a corresponding polynomial time algorithm that uses the model. We focus on a restricted class of graphs that occur in VLSI wire routing and show how to extend the algorithm to general planar graphs. We show how to take an arbitrary wire routing and convert it into a homotopic equivalent routing such that the distance between any two wires is maximized. Moreover, the routing uses the minimum length wires. Maximizing the distance between wires is equivalent to finding the drawing in which the edges are drawn as thick as possible. To the best of our knowledge this is the first algorithm that finds the maximal distance between any two wires and allows for wires of variable thickness. The previous best known result for the corresponding decision problem with unit wire thickness is the algorithm of Gao et al, which runs in O(kn 2 log(kn)) time and uses O(kn 2) space, where n is the number of wires and k is the maximum of the input and output complexities. The running time of our algorithm is O(kn + n 3) and the space required is O(k+n). The algorithm generalizes naturally to general planar graphs as well. © Springer-Verlag Berlin Heidelberg 2002.
• Efrat, A., & Har-Peled, S. (2002). Guarding galleries and terrains. IFIP Advances in Information and Communication Technology, 96, 181-192.
  More info

  Abstract: Let P be a simple 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 algorithms for finding the smallest set S of points of P so that each point of P is seen by at least one point of S. We also present similar algorithms for terrains and polygons with holes.
• Efrat, A., Erten, C., Kobourov, S., & Mitchell, J. (2002). Simultaneous Embedding of Planar Graphs. arXiv preprint cs/0206018.
• Efrat, A., Guibas, L. J., Har-Peled, S., Mitchell, J. S., & Murali, T. M. (2002). New similarity measures between polylines with applications to morphing and polygon sweeping. Discrete and Computational Geometry, 28(4), 535-569.
  More info

  Abstract: We introduce two new related metrics, the geodesic width and the link width, for measuring the "distance" between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O (n2 log n) time using O(n2) space and the link width in O(n3 log n) time using O(n2) working space where n is the total number of edges of the polylines. Our computation of these metrics relies on two closely related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path (resp., link) diagram encodes the Euclidean (resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems: Compute a continuous transformation that "morphs" one polyline into another polyline. Our morphing strategies ensure that each point on a polyline moves as little as necessary during the morphing, that every intermediate polyline is also simple and disjoint to any other intermediate polyline, and that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. We present an algorithm that computes the geodesic width of the two polylines and utilizes it to construct a corresponding morphing strategy in O(n2 log2 n) time using O(n2) space. We also give an O(n log n) time algorithm to compute a 2-approximation of the geodesic width and a corresponding morphing scheme. Locate a continuously moving target using a group of guards moving inside a simple polygon. The guards always determine a simple polygonal chain within the polygon, with consecutive guards along the chain being mutually visible. We compute a strategy that sweeps such a chain of guards through the polygon in order to locate a target. We compute in O(n3) time and O(n2) working space the minimum number r* of guards needed to sweep an n-vertex polygon. We also give an approximation algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r - 16, 2) ≤r* ≤ r and P can be swept with a chain of r guards.
• Efrat, A., Hoffmann, F., Kriegel, K., Schultz, C., & Wenk, C. (2002). Geometric algorithms for the analysis of 2D-electrophoresis gels. Journal of Computational Biology, 9(2), 299-315.
  More info

  PMID: 12015883;Abstract: In proteomics, two-dimensional gel electrophoresis (2-DE) is a separation technique for proteins. The resulting protein spots can be identified either by using picking robots and subsequent mass spectrometry or by visual cross inspection of a new gel image with an already analyzed master gel. Difficulties especially arise from inherent noise and irregular geometric distortions in 2-DE images. Aiming at the automated analysis of large series of 2-DE images, or at the even more difficult interlaboratory gel comparisons, the bottleneck is to solve the two most basic algorithmic problems with high quality: Identifying protein spots and computing a matching between two images. For the development of the analysis software CAROl at Freie Universitát Berlin, we have reconsidered these two problems and obtained new solutions which rely on methods from computational geometry. Their novelties are: 1. Spot detection is also possible for complex regions formed by several "merged" (usually saturated) spots; 2. User-defined landmarks are not necessary for the matching. Furthermore, images for comparison are allowed to represent different parts of the entire protein pattern, which only partially "overlap." The implementation is done in a client server architecture to allow queries via the internet. We also discuss and point at related theoretical questions in computational geometry.
• Efrat, A., Kobourov, S., Stepp, M., & Wenk, C. (2002). Growing fat graphs. Proceedings of the Annual Symposium on Computational Geometry, 277-278.
  More info

  Abstract: An algorithm for growing fat graphs with edges of variable thickness was presented. A restricted class of graphs, occurring in VLSI wire routing, was empolyed for demonstration. The general technique for finding the continuous homotopic of maximum separation was also discussed. A video, showing examples of graph growth illustrating merge, split and stopping events and the formation and breaking of bundles, was presented.
• Amir, A., Efrat, A., & Srinivasan, S. (2001). Advances in phonetic word spotting. International Conference on Information and Knowledge Management, Proceedings, 580-582.
  More info

  Abstract: Phonetic speech retrieval is used to augment word based retrieval in spoken document retrieval systems, for in and out of vocabulary words. In this paper, we present a new indexing and ranking scheme using metaphones and a Bayesian phonetic edit distance. We conduct an extensive set of experiments using a hundred hours of HUB4 data with ground truth transcript and twenty-four thousands query words. We show improvement of up to 15% in precision compare to results obtained speech recognition alone, at a processing time of 0.5 Sec per query.
• Amir, A., Efrat, A., Indyk, P., & Samet, H. (2001). Efficient regular data structures and algorithms for dilation, location, and proximity problems. Algorithmica (New York), 30(2), 164-187.
  More info

  Abstract: In this paper we investigate data structures obtained by a recursive partitioning of the multi-dimensional input domain into regions of equal size. One of the best known examples of such a structure is the quadtree. It is used here as a basis for more complex data structures. We also provide multidimensional versions of the stratified tree by van Emde Boas [vEB]. We show that under the assumption that the input points have limited precision (i.e., are drawn from the 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 dynamic approximate nearest neighbor (under insertions and deletions) and exact on-line closest pair (under insertions only) in any constant number of dimensions. 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 region quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the operation of dilation by a ball.
• Amir, A., Efrat, A., Indyk, P., & Samet, H. (2001). Efficient regular data structures and algorithms for dilation, location, and proximity problems. Algorithmica, 30(2), 164--187.
• Aronov, B., Efrat, A., Halperin, D., & Sharir, M. (2001). On the number of regular vertices of the union of Jordan regions. Discrete \& Computational Geometry, 25(2), 203--220.
• Aronov, B., Efrat, A., Halperin, D., & Sharir, M. (2001). On the number of regular vertices of the union of Jordan regions. Discrete and Computanional Geometry, 25(2), 203-220.
  More info

  Abstract: 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. If the boundaries of two sets in C cross exactly twice, then their intersection points are called regular vertices of the arrangement A(C). Let R(C) denote the set of regular vertices on the boundary of the union of C. We present several bounds on |R(C)|, depending on the type of the sets of C. (i) If each set of C is convex, then |R(C)| = O(n1.5+ε) for any ε > 0.1 (ii) If no further assumptions are made on the sets of C, then we show that there is a positive integer r that depends only on s such that |R(C)| = O(n2-1/r). (iii) If C consists of two collections C1 and C2 where C1 is a collection of m convex pseudo-disks in the plane (closed Jordan regions with the property that the boundaries of any two of them intersect at most twice), and C2 is a collection of polygons with a total of n sides, then |R(C)| = O(m2/3n2/3 + m + n), and this bound is tight in the worst case.
• Chan, T. M., & Efrat, A. (2001). Fly Cheaply: On the Minimum Fuel Consumption Problem. Journal of Algorithms, 41(2), 330-337.
  More info

  Abstract: In planning a flight, stops at intermediate airports are sometimes necessary to minimize fuel consumption, even if a direct flight is available. We investigate the problem of finding the cheapest path from one airport to another, given a set of n airports in ℝ2 and a function l: ℝ2 × ℝ2 → ℝ+ representing the cost of a direct flight between any pair. Given a source airport s, the cheapest-path map is a subdivision of ℝ2 where two points lie in the same region iff their cheapest paths from s use the same sequence of intermediate airports. We show a quadratic lower bound on the combinatorial complexity of this map for a class of cost functions. Nevertheless, we are able to obtain subquadratic algorithms to find the cheapest path from s to all other airports for any well-behaved cost function l: our general algorithm runs in O(n4/3+ε) time, and a simpler, more practical variant runs in O(n3/2+ε) time, while a special class of cost functions requires just O(n log n) time. © 2001 Elsevier Science.
• Chan, T. M., & Efrat, A. (2001). Fly cheaply: On the minimum fuel consumption problem. Journal of Algorithms, 41(2), 330--337.
• Davies, N., Cheverst, K., Mitchell, K., & Efrat, A. (2001). Using and determining location in a context-sensitive tour guide. Computer, 34(8), 35-41.
  More info

  Abstract: The Lancaster Guide project which used the members of the general public to test a network-centric electronic tourist guide was discussed. The study provided insights into the challenges associated with developing location-based applications. The guide relied on a geographic model that contained two distinct object types, which were navigation point objects and location objects. The end-user system of the guide provided capabilities such as access to information; tailored city tours; access to interactive services; and cooperative tools. Location information was obtained using technology such as the Global Positioning System (GPS) and the wireless network.
• Efrat, A., Har-Peled, S., Guibas, L. J., & Murali, T. M. (2001). Morphing between polylines. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 680-689.
  More info

  Abstract: Given two non-intersecting simple polylines in the plane, we study the problem of continuously transforming or morphing one polyline into the other. Our morphing strategies have the desirable property that every intermediate polyline is also simple. We also guarantee that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. Our algorithms are based on the morphing width, a new metric we have developed for measuring the similarity between two polylines. We develop an algorithm that computes the morphing width of the two polylines and constructs a corresponding morphing strategy in &Ogr;(n2 log 2 n) time using &Ogr;(n2) space, where n is the total number of vertices in the polylines. We describe another algorithm that computes a factor-2 approximation of the morphing width and a corresponding morphing scheme in &Ogr;(n log n) time. Copyright © 2009 ACM, Inc.
• Efrat, A., Hoffmann, F., Kriegel, K., Schultz, C., & Wenk, C. (2001). Geometric algorithms for the analysis of 2D-electrophoresis gels. Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB, 114-123.
  More info

  Abstract: 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 spectrometry or by visual cross inspection of a new gel image with an already analyzed master gel. Difficulties especially arise from inherent noise and irregular geometric distortions in 2-DE images. Aiming at the automated analysis of large series of 2-DE images, or at the even more difficult interlaboratory gel comparisons, the bottleneck is to solve the two most basic algorithmic problems with high quality: Identifying protein spots and computing a matching between two images. For the development of the analysis software CAROL at Freie Universität Berlin we have reconsidered these two problems and obtained new solutions which rely on methods from computational geometry. Their novelties are: 1. Spot detection is also possible for complex regions formed by several "merged" (usually saturated) spots; 2. User-defined landmarks are not necessary for the matching. Furthermore, images for comparison are allowed to represent different parts of the entire protein pattern, which only partially "overlap". The implementation is done in a client server architecture to allow queries via the Internet. We also discuss and point at rela ted theoretical questions in computational geometry.
• Efrat, A., Indyk, P., & Venkatasubramanian, S. (2001). Pattern matching for sets of segments. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 295-304.
  More info

  Abstract: 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 plain. Our work consists of two main parts. In the first, we address problems and measures that relate to collections of orthogonal line segments in the plane. Such collections arise naturally from problems in mapping buildings and robot exploration. We propose a new measure of segment similarity called a coverage measure, and present efficient algorithms for maximising this measure between sets of axis-parallel segments under translations. Our algorithms run in time &Ogr;(n 3polylogn) in the general case, and run in time &Ogr;(n 3polylogn) for the case when all segments are horizontal. In addition, we show that when restricted to translations that are only vertical, the Hausdorff distance between two sets of horizontal segments can be computed in time roughly &Ogr;(n 3/2polylog n). These algorithms are significant improvements over the general algorithm of Chew et al. that takes time &Ogr;(n 4 log 2 n). In the second part of this paper we address the problem of matching polygonal chains. We study the well known Fréchet distance, and present the first algorithm for computing the Fréchet distance under general translations. Our methods also yield algorithms for computing a generalization of the Fréchet distance, and we present a simple approximation algorithm for the Fréchet distance and its generalization that runs in time &Ogr;(n 2polylogn). Copyright © 2009 ACM, Inc.
• Efrat, A., Itai, A., & Katz, M. J. (2001). Geometry helps in bottleneck matching and related problems. Algorithmica (New York), 31(1), 1-28.
  More info

  Abstract: Let A and B be two sets of n objects in ℝd, and let Match be a (one-to-one) matching between A and B. Let min(Match), max.(Match), and σ(Match) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of Match, respectively. Bottleneck matching - a matching that minimizes max(Match) - is suggested as a convenient way for measuring the resemblance between A and B. Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is roughly O(n1.5). For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n1.5 log n). A semidynamic data structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Next, the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion is considered. When A and B are point-sets in the plane, an O(n5 log n)-time algorithm for determining whether for some translated copy the resemblance gets below a given ρ is presented, thus improving the previous result of Alt, Mehlhorn, Wagener, and Welzl by a factor of almost n. This result is used to compute the smallest such ρ in time O(n5 log2 n), and an efficient approximation scheme for this problem is also given. The uniform matching problem (also called the balanced assignment problem, or the fair matching problem) is to find Match*U, a matching that minimizes max(Match) - min(Match). A minimum deviation matching Match*D is a matching that minimizes (1/n)σ(Match) - min(Match). Algorithms for computing Match*U and Match*D in roughly O(n10/3) time are presented. These algorithms are more efficient than the previous O(n4)-time algorithms of Martello, Pulleyblank, Toth, and de Werra, and of Gupta and Punnen, who studied these problems for general bipartite graphs.
• Efrat, A., Itai, A., & Katz, M. J. (2001). Geometry helps in bottleneck matching and related problems. Algorithmica, 31(1), 1--28.
• Agarwal, P. K., Efrat, A., & Sharir, M. (2000). Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM Journal on Computing, 29(3), 912--953.
• Efrat, A., & Katz, M. J. (2000). Computing Euclidean bottleneck matchings in higher dimensions. Information Processing Letters, 75(4), 169-174.
  More info

  Abstract: We extend the planar results of Chang et al. (1992) to higher dimensions, and show that given a set A of 2n points in d-space it is possible to compute a Euclidean bottleneck matching of A in roughly O(n1.5) time, for d≤6, and in subquadratic time, for any constant d>6. If the underlying norm is L∞, then it is possible to compute a bottleneck matching of A in O(n1.5 log0.5 n) time, for any constant d≥2.
• Efrat, A., & Katz, M. J. (2000). Computing Euclidean bottleneck matchings in higher dimensions. Information processing letters, 75(4), 169--174.
• Efrat, A., & Sharir, M. (2000). On the complexity of the union of fat convex objects in the plane. Discrete \& Computational Geometry, 23(2), 171--189.
• Efrat, A., & Sharir, M. (2000). On the complexity of the union of fat convex objects in the plane. Discrete and Computanional Geometry, 23(2), 171-189.
  More info

  Abstract: 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.
• Efrat, A., Guibas, L. J., Hall-Holt, O. A., & Zhang, L. (2000). On incremental rendering of silhouette maps of a polyhedral scene. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 910-917.
  More info

  Abstract: 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 - hundreds of thousands or millions, but these may come from only a moderate number of objects that happen to have been finely tessellated. It is sometimes advantageous to render only the silhouettes of the objects, rather than the objects themselves, and then exploit coherence or other methods to optimize the rendering of single-object regions with uniform reflectance properties. Such an approach is also regularly used in the domain of non-photorealistic rendering, where the rendering of silhouette edges plays a key role. The hard part in efficiently implementing a kinetic approach to this problem is to realize when the rendered silhouette undergoes a combinatorial change. In this paper, we obtain bounds on a number of combinatorial problems involving the complexity of these events for a collection of k objects, with a total of n edges. We assume that our objects are convex polytopes, and that the viewpoint is moving along a straight line, or along an algebraic curve. The resulting bounds will then depend on both the number of objects, and the total number of edges, in such a way that we can describe the advantages of focusing on the silhouettes of combinatorially large objects. We also study the special case when the scene is a polyhedral terrain, and present improved bounds for this case. In addition to event bounds, we also obtain algorithms that compute all the changes occurring during a linear motion, (both for general scenes and for terrains).
• Efrat, A., Katz, M. J., Nielsen, F., & Sharir, M. (2000). Dynamic data structures for fat objects and their applications. Computational Geometry: Theory and Applications, 15(4), 215-227.
  More info

  Abstract: We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in ℝ2 or ℝ3. Our planar structures are actually fitted for a more general class of objects - (β, δ)-covered objects -which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor. © 2000 Elsevier Science B.V. All rights reserved.
• Efrat, A., Katz, M. J., Nielsen, F., & Sharir, M. (2000). Dynamic data structures for fat objects and their applications. Computational Geometry, 15(4), 215--227.
• Agarwal, P. K., Efrat, A., & Sharir, M. (1999). Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM Journal on Computing, 29(3), 912-953.
  More info

  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)-level of the arrangement A(F) is O(k3+ε ψ(n/k)) for any ε > 0, where ψ(r) is the maximum complexity of the lower envelope of a subset of at most r functions of F. This bound is nearly optimal in the worst case and implies the existence of shallow cuttings, in the sense of [J. Matousek, Comput. Geom., 2 (1992), pp. 169-186], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including (i) data structures for several generalized 3-dimensional range-searching problems; (ii) dynamic data structures for planar nearest- and farthest-neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.
• Amir, A., Efrat, A., Indyk, P., & Samet, H. (1999). Efficient regular data structures and algorithms for location and proximity problems. Annual Symposium on Foundations of Computer Science - Proceedings, 160-170.
  More info

  Abstract: 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 quadtree, used here as a basis for more complex data structures; we also provide multidimensional versions of the stratified tree by van Emde Boas. We show that under the assumption that the input points have limited precision (i.e. are drawn from the 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 dynamic approximate nearest neighbor (under insertions and deletions) and exact on-line 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.
• Chew, L. P., Dor, D., Efrat, A., & Kedem, K. (1999). Geometric pattern matching in d-dimensional space. Discrete \& Computational Geometry, 21(2), 257--274.
• Chew, L. P., Dor, D., Efrat, A., & Kedem, K. (1999). Geometric pattern matching in d-dimensional space. Discrete and Computational Geometry, 21(2), 257-274.
  More info

  Abstract: We show that, using the L∞ 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-2)/3 log2 n) for 3 < d ≤ 8, and in time O(n5d/4 log2 n) for any d > 8. Thus we improve the previous time bound of O(n2d-2 log2 n) due to Chew and Kedem. For d = 3 we obtain a better result of O(n3 log2 n) time by exploiting the fact that the union of n axis-parallel unit cubes can be decomposed into O(n) disjoint axis-parallel boxes. We prove that the number of different translations that achieve the minimum Hausdorff distance in d-space is Θ(n[3d/2]). Furthermore, we present an algorithm which computes the minimum Hausdorff distance under the L2 metric in d-space in time O(n[3d/2]+1+δ), for any δ > 0.
• Efrat, A. (1999). Complexity of the union of (α, β)-covered objects. Proceedings of the Annual Symposium on Computational Geometry, 134-142.
  More info

  Abstract: 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 at least α and all its edges are at least β·diam(c)-long. This notion extends that of fat convex objects. We show that the combinatorial complexity of the union of n (α, β)-covered objects of `constant description complexity' is O(λs+2(n) log2 n log log n), where s is the maximum number of intersections between the boundaries of any pair of the given objects.
• Efrat, A., & Katz, M. J. (1999). On the Union of $\kappa$-Curved Objects. Computational Geometry Theory and Applications, 14, 241--254.
• Efrat, A., & Har-Peled, S. (1998). Fly cheaply: On the minimum fuel-consumption problem. Proceedings of the Annual Symposium on Computational Geometry, 143-145.
  More info

  Abstract: The problem of planning the cheapest flight path, given s, t, and a set of intermediate airports at which it can make a stop is presented. This problem can be formalize by letting P be a set of n points in the plane, containing two given special points s and t. To solve the cheapest path problem in the setting, the Delaunay triangulation D(P) of P, in time O(n log n) is computed, and the shortest path problem on the graph D(P) under the cost function l(.,.) is solved using the standard Dijkstra's algorithm. Since the size of D is O(n) this implies that the overall running time of the algorithm is O(n log n).
• Efrat, A., & Katz, M. J. (1998). On the union of κ-curved objects. Proceedings of the Annual Symposium on Computational Geometry, 206-213.
  More info

  Abstract: A (not necessarily convex) object C in the plane is κ-curved for some constant κ, κ
• Efrat, A., & Schwarzkopf, O. (1997). Separating and shattering long line segments. Information Processing Letters, 64(6), 309-314.
  More info

  Abstract: 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 shatter S if each line of L is a separator for S, and every two objects of S are separated by at least one line of L. We give a simple randomized algorithm to construct the set of all separators for a given set S of n line segments in expected time O(n log n), provided the ratio between the diameter of S and the length of the shortest line segment is bounded by a constant. We also give a randomized algorithm to determine a set of lines shattering S, whose expected running time is O(n log n), improving (for this setting) the (deterministic) O(n2 log n) time algorithm of Freimer, Mitchell and Piatko. © 1997 Published by Elsevier Science B.V.
• Efrat, A., & Schwarzkopf, O. (1997). Separating and shattering long line segments. Information processing letters, 64(6), 309--314.
• Efrat, A., & Sharir, M. (1997). On the complexity of the union of fat objects in the plane. Proceedings of the Annual Symposium on Computational Geometry, 104-112.
  More info

  Abstract: 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.
• Efrat, A., & Itai, A. (1996). Improvements on bottleneck matching and related problems using geometry. Proceedings of the Annual Symposium on Computational Geometry, 301-310.
  More info

  Abstract: Let A and B be two sets of n objects in Rd. We propose to use bottleneck matching as a convenient way for measuring the resemblance between them, and present several algorithms for computing, as well as approximating, this resemblance. The running time of all these algorithms is close to O(n1.5). For instance, if the objects are points in the plane, the running time is O(n1.5 log n). We also consider the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion. When A and B are point-sets in the plane, we present an O(n5 log n) time algorithm for determining whether for some translated copy the resemblance gets below a given ρ, improving the previous result of Alt, Mehlhorn, Wagener and Welzl by a factor of almost n. We use this result to compute the smallest such ρ in time O(n5 log2 n), and give an efficient approximation scheme for this problem.
• Efrat, A., & Sharir, M. (1996). A near-linear algorithm for the planar segment-center problem. Discrete \& Computational Geometry, 16(3), 239--257.
• Efrat, A., & Sharir, M. (1996). A near-linear algorithm for the planar segment-center problem. Discrete and Computational Geometry, 16(3), 239-257.
  More info

  Abstract: 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 euclidean distance from e to the points of P. We present an algorithm that solves the problem in time O(n1+ε), for any ε > 0, improving the previous solution of Agarwal et al. [3] by nearly a factor of O(n).
• Efrat, A., & Gotsman, C. (1994). Subpixel image registration using circular fiducials. International Journal of Computational Geometry \& Applications, 4(04), 403--422.
• Efrat, A., & Sharir, M. (1994). Near-linear algorithm for the planar segment center problem. Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, 87-97.
  More info

  Abstract: 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) that minimizes the maximum euclidean distance from e to the points of P. We present an algorithm that solves the problem in time O(n log4 n log log n), improving the previous solution of Agarwal et al. by nearly a factor of O(n).
• Efrat, A., Sharir, M., & Ziv, A. (1994). Computing the smallest k-enclosing circle and related problems. Computational Geometry: Theory and Applications, 4(3), 119-136.
  More info

  Abstract: We present an efficient algorithm for solving the "smallest k-enclosing circle" (kSC) problem: Given a set of n points in the plane and an integer k ≤ n, find the smallest disk containing k of the points. We present two solutions. When using O(nk) storage, the problem can be solved in time O(nk log2 n). When only O(n log n) storage is allowed, the running time is O(nk log2 n log n/k). We also extend our technique to obtain efficient solutions of several related problems (with similar time and storage bounds). These related problems include: finding the smallest homothetic copy of a given convex polygon P which contains k points from a given planar set, and finding the smallest disk intersecting k segments from a given planar set of non-intersecting segments. © 1994.
• Efrat, A., Sharir, M., & Ziv, A. (1994). Computing the smallest k-enclosing circle and related problems. Computational Geometry, 4(3), 119--136.
• Agarwal, P. K., Efrat, A., Sharir, M., & Toledo, S. (1993). Computing a Segment Center for a Planar Point Set. Journal of Algorithms, 15(2), 314-323.
  More info

  Abstract: Given a set S of n points in the plane and a segment e, a center placement of e is a placement (allowing translation and rotation) that minimizes the maximum distance from e to the points of S. We present an algorithm for computing a center placement for S, whose running time is O(n2α(n)log3n), where α(n) is the inverse Ackermann function. The algorithm makes use of the parametric searching technique of Megiddo. © 1993 Academic Press. All rights reserved.
• Agarwal, P. K., Efrat, A., Sharir, M., & Toledo, S. (1993). Computing a segment center for a planar point set. Journal of Algorithms, 15(2), 314--323.
• Efrat, A., Rote, G., & Sharir, M. (1993). On the union of fat wedges and separating a collection of segments by a line. Computational Geometry: Theory and Applications, 3(5), 277-288.
  More info

  Abstract: We call a line l a separator for a set S of objects in the plane if l avoids all the objects and partitions S into two nonempty subsets, one consisting of objects lying above l and the other of objects lying below l. In this paper we present an O(n log n)-time algorithm for finding a separator line for a set of n segments, provided the ratio between the diameter of the set of segments and the length of the smallest segment is bounded. The general case is an 'n2-hard' problem, in the sense defined in [10] (see also [8]). Our algorithm is based on the recent results of [15], concerning the union of 'fat' triangles, but we also include an analysis which improves the bounds obtained in [15]. © 1993.
• Efrat, A., Rote, G., & Sharir, M. (1993). On the union of fat wedges and separating a collection of segments by a line. Computational Geometry, 3(5), 277--288.

Proceedings Publications

• Arkin, E. M., Sahneh, F. D., Efrat, A., Frank, F., Fulek, R., Kobourov, S., & Mitchell, J. S. (2020). Computing $beta$-Stretch Paths in Drawings of Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
• Efrat, A., Fulek, R., Kobourov, S. G., & Toth, C. (2020, Fall). Polygons with Prescribed Angles in 2D and 3D. In 28th International Symposium on Graph Drawing and Network Visualization (GD).
  More info

  This is an A-level conference in CORE.
• Pan, Y., Efrat, A., Li, M., Wang, B., Quan, H., Mitchell, J., Gao, J., & Arkin, E. M. (2020). Data inference from encrypted databases: a multi-dimensional order-preserving matching approach. In Mobihoc '20: The Twenty-first ACM International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, Virtual Event, USA, October 11-14, 2020.
• Mamano, N., Efrat, A., Eppstein, D., Frishberg, D., Goodrich, M. T., Kobourov, S. G., Matias, P., & Polishchuk, V. (2019). New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, 149.
• Ahmed, A. R., Angelini, P., Sahneh, F. D., Efrat, A., Glickenstein, D., Gronemann, M., Heinsohn, N., Kobourov, S. G., Spence, R., Watkins, J., & Wolff, A. (2018). Multi-Level Steiner Trees. In 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L'Aquila, Italy, 103.
• Angelakis, V., Efrat, A., Packer, E., Polishchuk, V., & Sedov, L. (2016). BBTM: New life for old ATM paradigms. In Digital Avionics Systems Conference (DASC), 2016 IEEE/AIAA 35th.
• Matsuura, E., Homma, S., Horiguchi, S., Matsumoto, S., & Okada, K. I. (2016). 2015 17th International Conference on E-Health Networking, Application and Services, HealthCom 2015. In Institute of Electrical and Electronics Engineers Inc..
• , ., , ., , ., & , . (2015). Algorithms for Sensor Systems - 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014, Wroclaw, Poland, September 12, 2014, Revised Selected Papers.
• Allouche, Y., Cassuto, Y., Efrat, A., Segal, M., Arkin, E., Grebla, G., & Mitchell, J. S. (2015). Secure Communication through Jammers Jointly Optimized in Geography and Time. In Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc.
• Arkin, E. M., Efrat, A., Knauer, C., Mitchell, J., Polishchuk, V., Rote, G., Schlipf, L., & Talvitie, T. (2015). Shortest Path to a Segment and Quickest Visibility Queries. In 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, 34.
• Arkin, E., Cassuto, Y., Efrat, A., Grebla, G., Mitchell, J. S., Sankararaman, S., & Segal, M. (2015). Optimal placement of protective jammers for securing wireless transmissions in a geographic domain. In Proceedings of the 14th International Conference on Information Processing in Sensor Networks.
• Grebla, G., Efrat, A., Ezra, E., Pinchasi, R., & Sankararaman, S. (2015). Data recovery after geographic correlated attacks. In 11th International Conference on the Design of Reliable Communication Networks, DRCN 2015, Kansas City, MO, USA, March 24-27, 2015.
• Liu, M., Agarwal, R., Richa, A., Efrat, A., Johnson, T., & Coutinho, M. M. (2015). Robust Data Mule Networks with Remote Healthcare Applications in the Amazon Region: A Fountain Code Approach. In IEEE 17th Int. Conf. n e-Health Networking, Applications and Services (Healthcom) 2015.
• Liu, M., Johnson, T., Agarwal, R., Efrat, A., Richa, A., & Coutinho, M. M. (2015). Robust data mule networks with remote healthcare applications in the Amazon region: A fountain code approach. In E-health Networking, Application \& Services (HealthCom), 2015 17th International Conference on.
• Sankararaman, G. G., Efrat, A., Ezra, E., Pinchasi, R., & Swaminathan, . (2015). Data recovery after geographic correlated attacks.. In IEEE 11th International Conference on the Design of Reliable Communication Networks, (DRCN).
• Arkin, E. M., Efraty, A., & Mitchell, J. S. (2014). Hybrid algorithms for scheduling sensors for guarding polygonal domains. In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG’14).
• Efrat, A., Hu, Y., Kobourov, S. G., & Pupyrev, S. (2014). MapSets: visualizing embedded and clustered graphs. In International Symposium on Graph Drawing.
• Efrat, A., Nikkil\"a, M., & Polishchuk, V. (2013). Sweeping a terrain by collaborative aerial vehicles. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.
• Qiyam, T. (2013). MobiSLIC: Content-Aware Energy Saving for Educational Videos on Mobile Devices. In MobiQuitous. 10th International Conference on Mobile and Ubiquitous Systems: Computing, Networking, and Services.
• Abu-Affash, K., Efrat, A., Sylvester, S. D., Polishchuk, V., Segal, M., & Sankararaman, S. (2012). Optimization Schemes for Protective Jamming. In MobiHoc '12 Proceedings of the thirteenth ACM international symposium on Mobile Ad Hoc Networking and Computing, 65--74.
• Efrat, A., Mitchell, J. S., Sankararaman, S., & Myers, P. (2012). Efficient algorithms for pursuing moving evaders in terrains. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems.
• Kharitonova, Y., Tung, Q., Danehy, A., Efrat, A., & Barnard, K. (2012). Client-side backprojection of presentation slides into educational video. In Proceedings of the 20th ACM international conference on Multimedia.
• Suh, Y., Moon, B., Efrat, A., Kim, J., & Lee, S. (2012). Extent mapping scheme for flash memory devices. In Modeling, Analysis \& Simulation of Computer and Telecommunication Systems (MASCOTS), 2012 IEEE 20th International Symposium on.
• Swaminathan Sankararaman, M. S., & Swaminathan Sankararaman, M. S. (2012). Optimization schemes for protective jamming. In The Thirteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '12.
• Zhang, P., Efrat, A., Sankararaman, S., & Wuzhou, . (2012). Nearest-neighbor searching under uncertainty. In Proceedings of the 31st symposium on Principles of Database Systems.
• Agarwal, P. K., Efrat, A., Gniady, C., Mitchell, J. S., Polishchuk, V., & Sabhnani, G. R. (2011). Distributed localization and clustering using data correlation and the Occam's razor principle. In Distributed Computing in Sensor Systems and Workshops (DCOSS), 2011 International Conference on.
• Coutinho, M. M., Moreira, T., Silva, E., Efrat, A., & Johnson, T. (2011). A new proposal of data mule network focused on amazon riverine population. In Proceedings of the 3rd Extreme Conference on Communication: The Amazon Expedition.
• Tung, Q., Swaminathan, R., Efrat, A., & Barnard, K. (2011). Expanding the point: automatic enlargement of presentation video elements. In Proceedings of the 19th ACM international conference on Multimedia.
• Agarwal, P. K., Agarwal, P. K., Efrat, A., Efrat, A., Ganjugunte, S. K., Ganjugunte, S. K., Hay, D., Hay, D., Sankararaman, S., Sankararaman, S., Zussman, G., & Zussman, G. (2010). Network vulnerability to single, multiple, and probabilistic physical attacks. In MILITARY COMMUNICATIONS CONFERENCE, 2010-MILCOM 2010.
• Swaminathan, R., Thompson, M. E., Fong, S., Efrat, A., Amir, A., & Barnard, K. (2010). Improving and aligning speech with presentation slides. In Pattern Recognition (ICPR), 2010 20th International Conference on.
• Winslow, A., Tung, Q., Fan, Q., Torkkola, J., Swaminathan, R., Barnard, K., Amir, A., Efrat, A., & Gniady, C. (2009). Studying on the move-enriched presentation video for mobile devices. In INFOCOM Workshops 2009, IEEE.
• Efrat, A., Fekete, S. P., Gaddehosur, P. R., Mitchell, J. S., Polishchuk, V., & Suomela, J. (2008). Improved approximation algorithms for relay placement. In European Symposium on Algorithms.
• Buchsbaum, A. L., Efrat, A., Jain, S., Venkatasubramanian, S., & Yi, K. e. (2007). Restricted strip covering and the sensor cover problem. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms.
• Fan, Q., Amir, A., Barnard, K., Swaminathan, R., & Efrat, A. (2007). Temporal modeling of slide change in presentation videos. In Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, 1.
• Polishchuk, V., Arkin, E. M., Aronov, B., Barnard, K., Coogan, K., Efrat, A., Mitchell, J. S., & Orlin, J. B. (2007). On matching robustness and geometric stable marriage. In Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT).
• Arkin, E., Efrat, A., Erten, C., Hurtado, F., Mitchell, J., Polishchuk, V., & Wenk, C. (2006). Shortest tour of a sequence of disjoint segments in L1. In Proc. 16th Fall Workshop on Computational and Combinatorial Geometry.
• Balasubramanian, R., Ramasubramanian, S., & Efrat, A. (2006). Coverage time characteristics in sensor networks. In Mobile Adhoc and Sensor Systems (MASS), 2006 IEEE International Conference on.
• Barnard, K., Connolly, A., Denneau, L., Efrat, A., Grav, T., Heasley, J., Jedicke, R., Kubica, J., Moon, B., Morris, S. H., & others, . (2006). The LSST moving object processing pipeline. In Observatory Operations: Strategies, Processes, and Systems, 6270.
• Fan, Q., Barnard, K., Amir, A., Efrat, A., & Lin, M. (2006). Matching slides to presentation videos using sift and scene background matching. In Proceedings of the 8th ACM international workshop on Multimedia information retrieval.
• Efrat, A., Har-Peled, S., & Mitchell, J. S. (2005). Approximation algorithms for two optimal location problems in sensor networks. In Broadband networks, 2005. BroadNets 2005. 2nd international conference on.
• Fan, Q., Efrat, A., Koltun, V., Krishnan, S., & Venkatasubramanian, S. (2005). Hardware-Assisted Natural Neighbor Interpolation.. In ALENEX/ANALCO.
• Alt, H., Efrat, A., Rote, G., & Wenk, C. (2003). Matching planar maps. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms.
• Dror, M., Efrat, A., Lubiw, A., & Mitchell, J. S. (2003). Touring a sequence of polygons. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing.
• Efrat, A., Gonz\'alez-Banos, H. H., Kobourov, S. G., & Palaniappan, L. (2003). Optimal strategies to track and capture a predictable target. In Robotics and Automation, 2003. Proceedings. ICRA'03. IEEE International Conference on, 3.
• Gonz\'alez-Banos, H., Efrat, A., Kobourov, S. G., & Palaniappan, L. (2003). Optimal motion strategies to track and capture a predictable target. In IEEE Conference of Robotics and Automation (ICRA).
• Wenk, C., Alt, H., Efrat, A., Palaniappan, L., & Rote, G. (2003). Finding a Curve in a Map. In Proceedings of the nineteenth annual symposium on Computational geometry.
• Efrat, A., Kobourov, S., Stepp, M., & Wenk, C. (2002). Growing fat graphs. In Proceedings of the eighteenth annual symposium on Computational geometry.
• Amir, A., Efrat, A., & Srinivasan, S. (2001). Advances in phonetic word spotting. In Proceedings of the tenth international conference on Information and knowledge management.
• Efrat, A., Har-Peled, S., Guibas, L. J., & Murali, T. M. (2001). Morphing between polylines. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms.
• Efrat, A., Indyk, P., & Venkatasubramanian, S. (2001). Pattern matching for sets of segments. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms.
• Efrat, A., Guibas, L. J., Har-Peled, S., Lin, D. C., Mitchell, J. S., & Murali, T. M. (2000). Sweeping simple polygons with a chain of guards. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms.
• Efrat, A., & Katz, M. (1996). Computing fair and bottleneck matchings in geometric graphs. In Algorithms and Computation, 7th International Symposium, ISAAC '96.
• Agarwal, P. K., Efrat, A., & Sharir, M. (1995). Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. In Proceedings of the eleventh annual symposium on Computational geometry.
• Bar-Yehuda, R., Efrat, A., & Itai, A. (1993). A Simple Algorithm for Maintaining the Center of a Planar Point-set.. In CCCG.
• Efrat, A., Lindenbaum, M., & Sharir, M. (1993). Finding Maximally Consistent Sets of Halfspaces.. In CCCG.

Others

• Krechetov, M., Sikaroudi, A., Efrat, A., Polishchuk, V., & Chertkov, M. (2021). Prediction and Prevention of Pandemics via Graphical Model Inference and Convex Programming.
• Packer, E., Pupyrev, S., Efrat, A., & Kobourov, S. (2018). Efficient Methods for Registration of Multiple Moving Points in Noisy Environments.
• Gao, J., Efrat, A., Fekete, S., Zhang, Y., & others, . (2015). Algorithms for Sensor Systems.
• Hua, X., Worring, M., & Chua, T. (2013). Internet Multimedia Search and Mining.
• Yao, J., Skowron, A., Wang, G., & Nguyen, H. S. (2013). Rough Sets and Knowledge Technology 2011 (RSKT'11) Preface.
• Amir, A., & Efrat, A. (2007). System and method for detecting proximity between mobile device users.
• Polishchuk, V., Arkin, E. M., Barnard, K., Coogan, K., Efrat, A., Mitchell, J. S., & Orlin, J. B. (2007). On matching robustness.
• Efrat, A., Guibasy, L. J., Har-Peledz, S., Linx, D. C., Mitchell, J. S., & Muralik, T. M. (1999). Sweeping Simple Polygons with a Chain of Guards.
• Bruckstein, A. M., Cohen, N., & Efrat, A. (1991). Ants, crickets and frogs in cyclic pursuit.