4 Search Results for "Mamano, Nil"

Document
DOI: 10.4230/LIPIcs.FUN.2021.4
Taming the Knight’s Tour: Minimizing Turns and Crossings

Authors: Juan Jose Besa, Timothy Johnson, Nil Mamano, and Martha C. Osegueda

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We introduce two new metrics of "simplicity" for knight’s tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.5n+O(1) turns and 13n+O(1) crossings on a n× n board, and we show lower bounds of (6-ε)n and 4n-O(1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 19/12+o(1) and 13/4+o(1). We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1,4)-leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases.
Cite as

Juan Jose Besa, Timothy Johnson, Nil Mamano, and Martha C. Osegueda. Taming the Knight’s Tour: Minimizing Turns and Crossings. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{besa_et_al:LIPIcs.FUN.2021.4,
  author =	{Besa, Juan Jose and Johnson, Timothy and Mamano, Nil and Osegueda, Martha C.},
  title =	{{Taming the Knight’s Tour: Minimizing Turns and Crossings}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.4},
  URN =		{urn:nbn:de:0030-drops-127654},
  doi =		{10.4230/LIPIcs.FUN.2021.4},
  annote =	{Keywords: Graph Drawing, Chess, Hamiltonian Cycle, Approximation Algorithms}
}
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-dev.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.ISAAC.2019.54
Tracking Paths in Planar Graphs

Authors: David Eppstein, Michael T. Goodrich, James A. Liu, and Pedro Matias

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

Abstract
We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et al. [Banik et al., 2017]. Given an undirected graph with a source s and a destination t, find the smallest subset of vertices whose intersection with any s-t path results in a unique sequence. In this paper, we show that this problem remains NP-complete when the graph is planar and we give a 4-approximation algorithm in this setting. We also show, via Courcelle’s theorem, that it can be solved in linear time for graphs of bounded-clique width, when its clique decomposition is given in advance.
Cite as

David Eppstein, Michael T. Goodrich, James A. Liu, and Pedro Matias. Tracking Paths in Planar Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ISAAC.2019.54,
  author =	{Eppstein, David and Goodrich, Michael T. and Liu, James A. and Matias, Pedro},
  title =	{{Tracking Paths in Planar Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{54:1--54:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.54},
  URN =		{urn:nbn:de:0030-drops-115500},
  doi =		{10.4230/LIPIcs.ISAAC.2019.54},
  annote =	{Keywords: Approximation Algorithm, Courcelle’s Theorem, Clique-Width, Planar, 3-SAT, Graph Algorithms, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.89
Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

Authors: Gill Barequet, David Eppstein, Michael T. Goodrich, and Nil Mamano

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We study algorithms and combinatorial complexity bounds for stable-matching Voronoi diagrams, where a set, S, of n point sites in the plane determines a stable matching between the points in R^2 and the sites in S such that (i) the points prefer sites closer to them and sites prefer points closer to them, and (ii) each site has a quota indicating the area of the set of points that can be matched to it. Thus, a stable-matching Voronoi diagram is a solution to the classic post office problem with the added (realistic) constraint that each post office has a limit on the size of its jurisdiction. Previous work provided existence and uniqueness proofs, but did not analyze its combinatorial or algorithmic complexity. We show that a stable-matching Voronoi diagram of n sites has O(n^{2+epsilon}) faces and edges, for any epsilon>0, and show that this bound is almost tight by giving a family of diagrams with Theta(n^2) faces and edges. We also provide a discrete algorithm for constructing it in O(n^3+n^2f(n)) time, where f(n) is the runtime of a geometric primitive that can be performed in the real-RAM model or can be approximated numerically. This is necessary, as the diagram cannot be computed exactly in an algebraic model of computation.
Cite as

Gill Barequet, David Eppstein, Michael T. Goodrich, and Nil Mamano. Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.ICALP.2018.89,
  author =	{Barequet, Gill and Eppstein, David and Goodrich, Michael T. and Mamano, Nil},
  title =	{{Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{89:1--89:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.89},
  URN =		{urn:nbn:de:0030-drops-90937},
  doi =		{10.4230/LIPIcs.ICALP.2018.89},
  annote =	{Keywords: Voronoi diagram, stable matching, combinatorial complexity, lower bounds}
}
  • Refine by Author
  • 3 Eppstein, David
  • 3 Goodrich, Michael T.
  • 3 Mamano, Nil
  • 2 Matias, Pedro
  • 1 Barequet, Gill
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Human-centered computing → Graph drawings
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 1 3-SAT
  • 1 Approximation Algorithm
  • 1 Approximation Algorithms
  • 1 Chess
  • 1 Clique-Width
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2019
  • 1 2018
  • 1 2020

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 Imprint Privacy Contact