Search Results

Documents authored by Efrat, Alon

Document
DOI: 10.4230/LIPIcs.SWAT.2020.7
Computing β-Stretch Paths in Drawings of Graphs

Authors: Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov, and Joseph S. B. Mitchell

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π=f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p∈P and q∈P, the length of the sub-curve of π connecting f(p) with f(q) is at most β||f(p)-f(q)‖, where ‖.‖ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. The βSP also asks that we output P if it exists. The βSP quantifies a notion of "near straightness" for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε>0, β∈O(poly(log |V(G)|)), and s,t∈V(G), outputs a β-stretch path between s and t, if a (1-ε)β-stretch path between s and t exists in the drawing.
Cite as

Esther M. Arkin, Faryad Darabi Sahneh, Alon Efrat, Fabian Frank, Radoslav Fulek, Stephen Kobourov, and Joseph S. B. Mitchell. Computing β-Stretch Paths in Drawings of Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.SWAT.2020.7,
  author =	{Arkin, Esther M. and Sahneh, Faryad Darabi and Efrat, Alon and Frank, Fabian and Fulek, Radoslav and Kobourov, Stephen and Mitchell, Joseph S. B.},
  title =	{{Computing \beta-Stretch Paths in Drawings of Graphs}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.7},
  URN =		{urn:nbn:de:0030-drops-122540},
  doi =		{10.4230/LIPIcs.SWAT.2020.7},
  annote =	{Keywords: stretch factor, dilation, geometric spanners}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.51
New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs

Authors: Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We use it to construct the greedy multi-fragment tour for Euclidean TSP in O(n log n) time in any fixed dimension and for Steiner TSP in planar graphs in O(n sqrt(n)log n) time; we compute motorcycle graphs, a central step in straight skeleton algorithms, in O(n^(4/3+epsilon)) time for any epsilon>0.
Cite as

Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk. New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mamano_et_al:LIPIcs.ISAAC.2019.51,
  author =	{Mamano, Nil and Efrat, Alon and Eppstein, David and Frishberg, Daniel and Goodrich, Michael T. and Kobourov, Stephen and Matias, Pedro and Polishchuk, Valentin},
  title =	{{New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.51},
  URN =		{urn:nbn:de:0030-drops-115477},
  doi =		{10.4230/LIPIcs.ISAAC.2019.51},
  annote =	{Keywords: Nearest-neighbors, Nearest-neighbor chain, motorcycle graph, straight skeleton, multi-fragment algorithm, Euclidean TSP, Steiner TSP}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.15
Multi-Level Steiner Trees

Authors: Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
In the classical Steiner tree problem, one is given an undirected, connected graph G=(V,E) with non-negative edge costs and a set of terminals T subseteq V. The objective is to find a minimum-cost edge set E' subseteq E that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of rho = ln(4)+epsilon < 1.39. In this paper, we study a natural generalization, the multi-level Steiner tree (MLST) problem: given a nested sequence of terminals T_1 subset ... subset T_k subseteq V, compute nested edge sets E_1 subseteq ... subseteq E_k subseteq E that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under names such as Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two natural heuristics with approximation factor O(k). Based on these, we introduce a composite algorithm that requires 2^k Steiner tree computations. We determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio and needs at most 2k Steiner tree computations. We compare five algorithms experimentally on several classes of graphs using four types of graph generators. We also implemented an integer linear program for MLST to provide ground truth. Our combined algorithm outperforms the others both in theory and in practice when the number of levels is small (k <= 22), which works well for applications such as designing multi-level infrastructure or network visualization.
Cite as

Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, and Alexander Wolff. Multi-Level Steiner Trees. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahmed_et_al:LIPIcs.SEA.2018.15,
  author =	{Ahmed, Reyan and Angelini, Patrizio and Sahneh, Faryad Darabi and Efrat, Alon and Glickenstein, David and Gronemann, Martin and Heinsohn, Niklas and Kobourov, Stephen G. and Spence, Richard and Watkins, Joseph and Wolff, Alexander},
  title =	{{Multi-Level Steiner Trees}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.15},
  URN =		{urn:nbn:de:0030-drops-89506},
  doi =		{10.4230/LIPIcs.SEA.2018.15},
  annote =	{Keywords: Approximation algorithm, Steiner tree, multi-level graph representation}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.658
Shortest Path to a Segment and Quickest Visibility Queries

Authors: Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.
Cite as

Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie. Shortest Path to a Segment and Quickest Visibility Queries. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 658-673, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.SOCG.2015.658,
  author =	{Arkin, Esther M. and Efrat, Alon and Knauer, Christian and Mitchell, Joseph S. B. and Polishchuk, Valentin and Rote, G\"{u}nter and Schlipf, Lena and Talvitie, Topi},
  title =	{{Shortest Path to a Segment and Quickest Visibility Queries}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{658--673},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.658},
  URN =		{urn:nbn:de:0030-drops-51474},
  doi =		{10.4230/LIPIcs.SOCG.2015.658},
  annote =	{Keywords: path planning, visibility, query structures and complexity, persistent data structures, continuous Dijkstra}
}
Document
DOI: 10.4230/DagSemProc.05361.7
Force-Directed Approaches to Sensor Network Localization

Authors: Stephen G. Kobourov, Alon Efrat, David Forrester, and Anand Iyer

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
In many sensor network applications it is necessary to compute low-error localization of the sensor nodes. Although embedding a GPS unit on each node would solve the problem for many outdoor applications, the cost of this solution for large networks is prohibitively high. We consider static and mobile network localization approaches that make use of the local neighborhood information, in the form of relative distances and angles to nearby nodes, gathered through simpler and less costly devices (RF, ultrasound based range sensors, or antenna arrays). Our algorithms do not make any assumptions about the existence of anchor nodes capable of locating themselves, nor about the knowledge of an initial localization to start with. Instead, we rely on a multi-scale force-directed approach, utilizing range and angle data through dead reckoning. We show that our localization algorithms are robust and scale well with network size.
Cite as

Stephen G. Kobourov, Alon Efrat, David Forrester, and Anand Iyer. Force-Directed Approaches to Sensor Network Localization. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kobourov_et_al:DagSemProc.05361.7,
  author =	{Kobourov, Stephen G. and Efrat, Alon and Forrester, David and Iyer, Anand},
  title =	{{Force-Directed Approaches to Sensor Network Localization}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.7},
  URN =		{urn:nbn:de:0030-drops-5693},
  doi =		{10.4230/DagSemProc.05361.7},
  annote =	{Keywords: Sensor network localization, multi-scale force-directed approach, dead reckoning}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact