Search Results

Documents authored by Maheshwari, Anil

Document
DOI: 10.4230/LIPIcs.GD.2024.36
Noncrossing Longest Paths and Cycles

Authors: Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.
Cite as

Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr. Noncrossing Longest Paths and Cycles. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aloupis_et_al:LIPIcs.GD.2024.36,
  author =	{Aloupis, Greg and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Eppstein, David and Maheshwari, Anil and Odak, Saeed and Smid, Michiel and T\'{o}th, Csaba D. and Valtr, Pavel},
  title =	{{Noncrossing Longest Paths and Cycles}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.36},
  URN =		{urn:nbn:de:0030-drops-213203},
  doi =		{10.4230/LIPIcs.GD.2024.36},
  annote =	{Keywords: Longest Paths, Longest Cycles, Noncrossing Paths, Noncrossing Cycles}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.7
Geometric Covering via Extraction Theorem

Authors: Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, and Kasturi Varadarajan

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
In this work, we address the following question. Suppose we are given a set D of positive-weighted disks and a set T of n points in the plane, such that each point of T is contained in at least two disks of D. Then is there always a subset S of D such that the union of the disks in S contains all the points of T and the total weight of the disks of D that are not in S is at least a constant fraction of the total weight of the disks in D? In our work, we prove the Extraction Theorem that answers this question in the affirmative. Our constructive proof heavily exploits the geometry of disks, and in the process, we make interesting connections between our work and the literature on local search for geometric optimization problems. The Extraction Theorem helps to design the first polynomial-time O(1)-approximations for two important geometric covering problems involving disks.
Cite as

Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, and Kasturi Varadarajan. Geometric Covering via Extraction Theorem. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.ITCS.2024.7,
  author =	{Bandyapadhyay, Sayan and Maheshwari, Anil and Roy, Sasanka and Smid, Michiel and Varadarajan, Kasturi},
  title =	{{Geometric Covering via Extraction Theorem}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.7},
  URN =		{urn:nbn:de:0030-drops-195355},
  doi =		{10.4230/LIPIcs.ITCS.2024.7},
  annote =	{Keywords: Covering, Extraction theorem, Double-disks, Submodularity, Local search}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.18
Half-Guarding Weakly-Visible Polygons and Terrains

Authors: Nandhana Duraisamy, Hannah Miller Hillberg, Ramesh K. Jallu, Erik Krohn, Anil Maheshwari, Subhas C. Nandy, and Alex Pahlow

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We consider a variant of the art gallery problem where all guards are limited to seeing 180degree. Guards that can only see in one direction are called half-guards. We give a polynomial time approximation scheme for vertex guarding the vertices of a weakly-visible polygon with half-guards. We extend this to vertex guarding the boundary of a weakly-visible polygon with half-guards. We also show NP-hardness for vertex guarding a weakly-visible polygon with half-guards. Lastly, we show that the orientation of half-guards is critical in terrain guarding. Depending on the orientation of the half-guards, the problem is either very easy (polynomial time solvable) or very hard (NP-hard).
Cite as

Nandhana Duraisamy, Hannah Miller Hillberg, Ramesh K. Jallu, Erik Krohn, Anil Maheshwari, Subhas C. Nandy, and Alex Pahlow. Half-Guarding Weakly-Visible Polygons and Terrains. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{duraisamy_et_al:LIPIcs.FSTTCS.2022.18,
  author =	{Duraisamy, Nandhana and Hillberg, Hannah Miller and Jallu, Ramesh K. and Krohn, Erik and Maheshwari, Anil and Nandy, Subhas C. and Pahlow, Alex},
  title =	{{Half-Guarding Weakly-Visible Polygons and Terrains}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.18},
  URN =		{urn:nbn:de:0030-drops-174103},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.18},
  annote =	{Keywords: Art Gallery Problem, Approximation Algorithm, NP-Hardness, Monotone Polygons, Half-Guards}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.44
Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane

Authors: Sayan Bandyapadhyay, Anil Maheshwari, and Michiel Smid

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Given two sets S and T of points in the plane, of total size n, a many-to-many matching between S and T is a set of pairs (p,q) such that p ∈ S, q ∈ T and for each r ∈ S ∪ T, r appears in at least one such pair. The cost of a pair (p,q) is the (Euclidean) distance between p and q. In the minimum-cost many-to-many matching problem, the goal is to compute a many-to-many matching such that the sum of the costs of the pairs is minimized. This problem is a restricted version of minimum-weight edge cover in a bipartite graph, and hence can be solved in O(n³) time. In a more restricted setting where all the points are on a line, the problem can be solved in O(nlog n) time [Justin Colannino et al., 2007]. However, no progress has been made in the general planar case in improving the cubic time bound. In this paper, we obtain an O(n²⋅ poly(log n)) time exact algorithm and an O(n^{3/2}⋅ poly(log n)) time (1+ε)-approximation in the planar case.
Cite as

Sayan Bandyapadhyay, Anil Maheshwari, and Michiel Smid. Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.ISAAC.2021.44,
  author =	{Bandyapadhyay, Sayan and Maheshwari, Anil and Smid, Michiel},
  title =	{{Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.44},
  URN =		{urn:nbn:de:0030-drops-154779},
  doi =		{10.4230/LIPIcs.ISAAC.2021.44},
  annote =	{Keywords: Many-to-many matching, bipartite, planar, geometric, approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.14
Bounded-Angle Minimum Spanning Trees

Authors: Ahmad Biniaz, Prosenjit Bose, Anna Lubiw, and Anil Maheshwari

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

Abstract
Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let α be an angle. An α-ST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p ∈ P lie in a wedge of angle α centered at p. We study the following closely related problems for α = 120 degrees (however, our approximation ratios hold for any α ⩾ 120 degrees). 1) The α-minimum spanning tree problem asks for an α-ST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NP-hardness of this problem and presented a 6-approximation algorithm. Their algorithm finds an α-ST of length at most 6 times the length of the minimum spanning tree (MST). By adopting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3. 2) To examine what is possible with non-uniform wedge angles, we define an ̅α-ST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle α. We present an algorithm to find an ̅α-ST whose largest edge-length and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle α. Our algorithm runs in linear time after computing the MST.
Cite as

Ahmad Biniaz, Prosenjit Bose, Anna Lubiw, and Anil Maheshwari. Bounded-Angle Minimum Spanning Trees. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SWAT.2020.14,
  author =	{Biniaz, Ahmad and Bose, Prosenjit and Lubiw, Anna and Maheshwari, Anil},
  title =	{{Bounded-Angle Minimum Spanning Trees}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{14:1--14:22},
  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.14},
  URN =		{urn:nbn:de:0030-drops-122616},
  doi =		{10.4230/LIPIcs.SWAT.2020.14},
  annote =	{Keywords: bounded-angle MST, directional antenna, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.37
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames

Authors: Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, and Subhash Suri

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-logarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NP-hard even when all the rectangles are "anchored" at a diagonal line with slope -1 (Pandit, CCCG 2017). In this paper, we first show that for any epsilon>0, there exists a (2+epsilon)-approximation algorithm for the MDS problem on "diagonal-anchored" rectangles, providing the first O(1)-approximation for the problem on a non-trivial subclass of rectangles. It is not hard to see that the MDS problem on "diagonal-anchored" rectangles is the same as the MDS problem on "diagonal-anchored" L-frames: the union of a vertical and a horizontal line segment that share an endpoint. As such, we also obtain a (2+epsilon)-approximation for the problem with "diagonal-anchored" L-frames. On the other hand, we show that the problem is APX-hard in case the input L-frames intersect the diagonal, or the horizontal segments of the L-frames intersect a vertical line. However, as we show, the problem is linear-time solvable in case the L-frames intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the so-called "edge intersection model" and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017).
Cite as

Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, and Subhash Suri. Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.MFCS.2018.37,
  author =	{Bandyapadhyay, Sayan and Maheshwari, Anil and Mehrabi, Saeed and Suri, Subhash},
  title =	{{Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.37},
  URN =		{urn:nbn:de:0030-drops-96198},
  doi =		{10.4230/LIPIcs.MFCS.2018.37},
  annote =	{Keywords: Minimum dominating set, Rectangles and L-frames, Approximation schemes, Local search, APX-hardness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.2
Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

Authors: A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.
Cite as

A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky. Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abuaffash_et_al:LIPIcs.SoCG.2018.2,
  author =	{Abu-Affash, A. Karim and Carmi, Paz and Maheshwari, Anil and Morin, Pat and Smid, Michiel and Smorodinsky, Shakhar},
  title =	{{Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.2},
  URN =		{urn:nbn:de:0030-drops-87152},
  doi =		{10.4230/LIPIcs.SoCG.2018.2},
  annote =	{Keywords: Approximation algorithms, maximum diameter-bounded subgraph, unit disk graphs, fractional Helly theorem, VC-dimension}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.8
Faster Algorithms for some Optimization Problems on Collinear Points

Authors: Ahmad Biniaz, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Ian Munro, and Michiel Smid

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We propose faster algorithms for the following three optimization problems on n collinear points, i.e., points in dimension one. The first two problems are known to be NP-hard in higher dimensions. 1) Maximizing total area of disjoint disks: In this problem the goal is to maximize the total area of nonoverlapping disks centered at the points. Acharyya, De, and Nandy (2017) presented an O(n^2)-time algorithm for this problem. We present an optimal Theta(n)-time algorithm. 2) Minimizing sum of the radii of client-server coverage: The n points are partitioned into two sets, namely clients and servers. The goal is to minimize the sum of the radii of disks centered at servers such that every client is in some disk, i.e., in the coverage range of some server. Lev-Tov and Peleg (2005) presented an O(n^3)-time algorithm for this problem. We present an O(n^2)-time algorithm, thereby improving the running time by a factor of Theta(n). 3) Minimizing total area of point-interval coverage: The n input points belong to an interval I. The goal is to find a set of disks of minimum total area, covering I, such that every disk contains at least one input point. We present an algorithm that solves this problem in O(n^2) time.
Cite as

Ahmad Biniaz, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Ian Munro, and Michiel Smid. Faster Algorithms for some Optimization Problems on Collinear Points. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SoCG.2018.8,
  author =	{Biniaz, Ahmad and Bose, Prosenjit and Carmi, Paz and Maheshwari, Anil and Munro, Ian and Smid, Michiel},
  title =	{{Faster Algorithms for some Optimization Problems on Collinear Points}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.8},
  URN =		{urn:nbn:de:0030-drops-87219},
  doi =		{10.4230/LIPIcs.SoCG.2018.8},
  annote =	{Keywords: collinear points, range assignment}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.11
Flip Distance to some Plane Configurations

Authors: Ahmad Biniaz, Anil Maheshwari, and Michiel Smid

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We study an old geometric optimization problem in the plane. Given a perfect matching M on a set of n points in the plane, we can transform it to a non-crossing perfect matching by a finite sequence of flip operations. The flip operation removes two crossing edges from M and adds two non-crossing edges. Let f(M) and F(M) denote the minimum and maximum lengths of a flip sequence on M, respectively. It has been proved by Bonnet and Miltzow (2016) that f(M)=O(n^2) and by van Leeuwen and Schoone (1980) that F(M)=O(n^3). We prove that f(M)=O(n Delta) where Delta is the spread of the point set, which is defined as the ratio between the longest and the shortest pairwise distances. This improves the previous bound for point sets with sublinear spread. For a matching M on n points in convex position we prove that f(M)=n/2-1 and F(M)={{n/2} choose 2}; these bounds are tight. Any bound on F(*) carries over to the bichromatic setting, while this is not necessarily true for f(*). Let M' be a bichromatic matching. The best known upper bound for f(M') is the same as for F(M'), which is essentially O(n^3). We prove that f(M')<=slant n-2 for points in convex position, and f(M')= O(n^2) for semi-collinear points. The flip operation can also be defined on spanning trees. For a spanning tree T on a convex point set we show that f(T)=O(n log n).
Cite as

Ahmad Biniaz, Anil Maheshwari, and Michiel Smid. Flip Distance to some Plane Configurations. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SWAT.2018.11,
  author =	{Biniaz, Ahmad and Maheshwari, Anil and Smid, Michiel},
  title =	{{Flip Distance to some Plane Configurations}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.11},
  URN =		{urn:nbn:de:0030-drops-88371},
  doi =		{10.4230/LIPIcs.SWAT.2018.11},
  annote =	{Keywords: flip distance, non-crossing edges, perfect matchings, spanning trees}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.19
Towards Plane Spanners of Degree 3

Authors: Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Let S be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane frac{3+4 pi}{3}-spanner of S whose vertex degree is at most 3. Let Lambda be the vertex set of a finite non-uniform rectangular lattice in the plane. We present an algorithm that constructs a plane 3 sqrt{2}-spanner for Lambda whose vertex degree is at most 3. For points that are in the plane and in general position, we show how to compute plane degree-3 spanners with a linear number of Steiner points.
Cite as

Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid. Towards Plane Spanners of Degree 3. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.ISAAC.2016.19,
  author =	{Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Gavoille, Cyril and Maheshwari, Anil and Smid, Michiel},
  title =	{{Towards Plane Spanners of Degree 3}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.19},
  URN =		{urn:nbn:de:0030-drops-67887},
  doi =		{10.4230/LIPIcs.ISAAC.2016.19},
  annote =	{Keywords: plane spanners, degree-3 spanners, convex position, non-uniform lattice}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.25
A Plane 1.88-Spanner for Points in Convex Position

Authors: Mahdi Amani, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, and Michiel Smid

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
Let S be a set of n points in the plane that is in convex position. For a real number t>1, we say that a point p in S is t-good if for every point q of S, the shortest-path distance between p and q along the boundary of the convex hull of S is at most t times the Euclidean distance between p and q. We prove that any point that is part of (an approximation to) the diameter of S is 1.88-good. Using this, we show how to compute a plane 1.88-spanner of S in O(n) time, assuming that the points of S are given in sorted order along their convex hull. Previously, the best known stretch factor for plane spanners was 1.998 (which, in fact, holds for any point set, i.e., even if it is not in convex position).
Cite as

Mahdi Amani, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, and Michiel Smid. A Plane 1.88-Spanner for Points in Convex Position. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{amani_et_al:LIPIcs.SWAT.2016.25,
  author =	{Amani, Mahdi and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Maheshwari, Anil and Smid, Michiel},
  title =	{{A Plane 1.88-Spanner for Points in Convex Position}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.25},
  URN =		{urn:nbn:de:0030-drops-60474},
  doi =		{10.4230/LIPIcs.SWAT.2016.25},
  annote =	{Keywords: points in convex position, plane spanner}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.26
Approximating the Integral Fréchet Distance

Authors: Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We present a pseudo-polynomial time (1 + epsilon)-approximation algorithm for computing the integral and average Fréchet distance between two given polygonal curves T_1 and T_2. The running time is in O(zeta^{4}n^4/epsilon^2) where n is the complexity of T_1 and T_2 and zeta is the maximal ratio of the lengths of any pair of segments from T_1 and T_2. Furthermore, we give relations between weighted shortest paths inside a single parameter cell C and the monotone free space axis of C. As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.
Cite as

Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Approximating the Integral Fréchet Distance. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{maheshwari_et_al:LIPIcs.SWAT.2016.26,
  author =	{Maheshwari, Anil and Sack, J\"{o}rg-R\"{u}diger and Scheffer, Christian},
  title =	{{Approximating the Integral Fr\'{e}chet Distance}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.26},
  URN =		{urn:nbn:de:0030-drops-60485},
  doi =		{10.4230/LIPIcs.SWAT.2016.26},
  annote =	{Keywords: Fr\'{e}chet distance, partial Fr\'{e}chet similarity, curve matching}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.27
Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts

Authors: Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We seek to augment a geometric network in the Euclidean plane with shortcuts to minimize its continuous diameter, i.e., the largest network distance between any two points on the augmented network. Unlike in the discrete setting where a shortcut connects two vertices and the diameter is measured between vertices, we take all points along the edges of the network into account when placing a shortcut and when measuring distances in the augmented network. We study this network augmentation problem for paths and cycles. For paths, we determine an optimal shortcut in linear time. For cycles, we show that a single shortcut never decreases the continuous diameter and that two shortcuts always suffice to reduce the continuous diameter. Furthermore, we characterize optimal pairs of shortcuts for convex and non-convex cycles. Finally, we develop a linear time algorithm that produces an optimal pair of shortcuts for convex cycles. Apart from the algorithms, our results extend to rectifiable curves. Our work reveals some of the underlying challenges that must be overcome when addressing the discrete version of this network augmentation problem, where we minimize the discrete diameter of a network with shortcuts that connect only vertices.
Cite as

Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid. Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{decarufel_et_al:LIPIcs.SWAT.2016.27,
  author =	{De Carufel, Jean-Lou and Grimm, Carsten and Maheshwari, Anil and Smid, Michiel},
  title =	{{Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.27},
  URN =		{urn:nbn:de:0030-drops-60492},
  doi =		{10.4230/LIPIcs.SWAT.2016.27},
  annote =	{Keywords: Network Augmentation, Shortcuts, Diameter, Paths, Cycles}
}
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