Alon Efrat

Alon Efrat

Auto-generated profile, based on publicly available information

Alon Efrat

Department of Computer Science, University of Arizona, Tucson, USA

Research Focus & Metrics

Academic Career Length

34Years (1993-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 September 2001 in Algorithmica
Verified
Journal Article
Closed access
PDF file
AEA. Efrat
A. Efrat
AIA. Itai
A. Itai
MKM. J. Katz
M. J. Katz

1 October 2013 in IEEE/ACM Transactions on Networking
Verified
Journal Article
Closed access
PAPankaj K. Agarwal
Pankaj K. Agarwal
AEAlon Efrat
Alon Efrat
SGShashidhara K. Ganjugunte
Shashidhara K. Ganjugunte
DHDavid Hay
David Hay
SSSwaminathan Sankararaman
Swaminathan Sankararaman
GZGil Zussman
Gil Zussman
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.

1 November 2003 in Journal of Algorithms
Verified
Journal Article
Closed access
HAHelmut Alt
Helmut Alt
AEAlon Efrat
Alon Efrat
GRGünter Rote
Günter Rote
CWCarola Wenk
Carola Wenk

30 November 2006 in Journal of Mathematical Imaging and Vision
Verified
Journal Article
Closed access
PDF file
AEAlon Efrat
Alon Efrat
QFQuanfu Fan
Quanfu Fan
SVSuresh Venkatasubramanian
Suresh Venkatasubramanian

1 February 2007 in Computational Geometry
Verified
Journal Article
Closed access
PBPeter Brass
Peter Brass
ECEowyn Cenek
Eowyn Cenek
CDCristian A. Duncan
Cristian A. Duncan
AEAlon Efrat
Alon Efrat
CECesim Erten
Cesim Erten
JMJoseph S.B. Mitchell
Joseph S.B. Mitchell

1 January 2000 in SIAM Journal on Computing
Verified
Journal Article
Closed access
PAPankaj K. Agarwal
Pankaj K. Agarwal
AEAlon Efrat
Alon Efrat
MSMicha Sharir
Micha Sharir
Let ${\cal 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 $({\le}k)$-level of the arrangement $\A({\cal F})$ is $O(k^{3+\varepsilon}\psi({n/k}))$ for any $\varepsilon>0$, where $\psi (r)$ is the maximum complexity of the lower envelope of a subset of at most r functions of ${\cal 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.