9 Search Results for "Agarwal, Pankaj Kumar"


Document
Computing Shortest Paths in the Plane with Removable Obstacles

Authors: Pankaj K. Agarwal, Neeraj Kumar, Stavros Sintos, and Subhash Suri

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


Abstract
We consider the problem of computing a Euclidean shortest path in the presence of removable obstacles in the plane. In particular, we have a collection of pairwise-disjoint polygonal obstacles, each of which may be removed at some cost c_i > 0. Given a cost budget C > 0, and a pair of points s, t, which obstacles should be removed to minimize the path length from s to t in the remaining workspace? We show that this problem is NP-hard even if the obstacles are vertical line segments. Our main result is a fully-polynomial time approximation scheme (FPTAS) for the case of convex polygons. Specifically, we compute an (1 + epsilon)-approximate shortest path in time O({nh}/{epsilon^2} log n log n/epsilon) with removal cost at most (1+epsilon)C, where h is the number of obstacles, n is the total number of obstacle vertices, and epsilon in (0, 1) is a user-specified parameter. Our approximation scheme also solves a shortest path problem for a stochastic model of obstacles, where each obstacle's presence is an independent event with a known probability. Finally, we also present a data structure that can answer s-t path queries in polylogarithmic time, for any pair of points s, t in the plane.

Cite as

Pankaj K. Agarwal, Neeraj Kumar, Stavros Sintos, and Subhash Suri. Computing Shortest Paths in the Plane with Removable Obstacles. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SWAT.2018.5,
  author =	{Agarwal, Pankaj K. and Kumar, Neeraj and Sintos, Stavros and Suri, Subhash},
  title =	{{Computing Shortest Paths in the Plane with Removable Obstacles}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{5:1--5:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.5},
  URN =		{urn:nbn:de:0030-drops-88312},
  doi =		{10.4230/LIPIcs.SWAT.2018.5},
  annote =	{Keywords: Euclidean shortest paths, Removable polygonal obstacles, Stochastic shortest paths, L\underline1 shortest paths}
}
Document
Efficient Algorithms for k-Regret Minimizing Sets

Authors: Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)


Abstract
A regret minimizing set Q is a small size representation of a much larger database P so that user queries executed on Q return answers whose scores are not much worse than those on the full dataset. In particular, a k-regret minimizing set has the property that the regret ratio between the score of the top-1 item in Q and the score of the top-k item in P is minimized, where the score of an item is the inner product of the item's attributes with a user's weight (preference) vector. The problem is challenging because we want to find a single representative set Q whose regret ratio is small with respect to all possible user weight vectors. We show that k-regret minimization is NP-Complete for all dimensions d>=3, settling an open problem from Chester et al. [VLDB 2014]. Our main algorithmic contributions are two approximation algorithms, both with provable guarantees, one based on coresets and another based on hitting sets. We perform extensive experimental evaluation of our algorithms, using both real-world and synthetic data, and compare their performance against the solution proposed in [VLDB 14]. The results show that our algorithms are significantly faster and scalable to much larger sets than the greedy algorithm of Chester et al. for comparable quality answers.

Cite as

Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri. Efficient Algorithms for k-Regret Minimizing Sets. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SEA.2017.7,
  author =	{Agarwal, Pankaj K. and Kumar, Nirman and Sintos, Stavros and Suri, Subhash},
  title =	{{Efficient Algorithms for k-Regret Minimizing Sets}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.7},
  URN =		{urn:nbn:de:0030-drops-76321},
  doi =		{10.4230/LIPIcs.SEA.2017.7},
  annote =	{Keywords: regret minimizing sets, skyline, top-k query, coreset, hitting set}
}
Document
Computational Geometry (Dagstuhl Seminar 11111)

Authors: Pankaj Kumar Agarwal, Kurt Mehlhorn, and Monique Teillaud

Published in: Dagstuhl Reports, Volume 1, Issue 3 (2011)


Abstract
This report documents the outcomes of Dagstuhl Seminar 11111 ``Computational Geometry''. The Seminar gathered fifty-three senior and younger researchers from various countries in the unique atmosphere offered by Schloss Dagstuhl. Abstracts of talks are collected in this report as well as a list of open problems.

Cite as

Pankaj Kumar Agarwal, Kurt Mehlhorn, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 11111). In Dagstuhl Reports, Volume 1, Issue 3, pp. 19-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@Article{agarwal_et_al:DagRep.1.3.19,
  author =	{Agarwal, Pankaj Kumar and Mehlhorn, Kurt and Teillaud, Monique},
  title =	{{Computational Geometry (Dagstuhl Seminar 11111)}},
  pages =	{19--41},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{3},
  editor =	{Agarwal, Pankaj Kumar and Mehlhorn, Kurt and Teillaud, Monique},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.3.19},
  URN =		{urn:nbn:de:0030-drops-31997},
  doi =		{10.4230/DagRep.1.3.19},
  annote =	{Keywords: Algorithms, geometry, combinatorics, topology, theory, applications, implementation}
}
Document
09111 Abstracts Collection – Computational Geometry

Authors: Pankaj Kumar Agarwal, Helmut Alt, and Monique Teillaud

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)


Abstract
From March 8 to March 13, 2009, the Dagstuhl Seminar 09111 ``Computational Geometry '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Pankaj Kumar Agarwal, Helmut Alt, and Monique Teillaud. 09111 Abstracts Collection – Computational Geometry. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:DagSemProc.09111.1,
  author =	{Agarwal, Pankaj Kumar and Alt, Helmut and Teillaud, Monique},
  title =	{{09111 Abstracts Collection – Computational Geometry}},
  booktitle =	{Computational Geometry},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.1},
  URN =		{urn:nbn:de:0030-drops-20346},
  doi =		{10.4230/DagSemProc.09111.1},
  annote =	{Keywords: }
}
Document
Two Applications of Point Matching

Authors: Günter Rote

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)


Abstract
The two following problems can be solved by a reduction to a minimum-weight bipartite matching problem (or a related network flow problem): a) Floodlight illumination: We are given $n$ infinite wedges (sectors, spotlights) that can cover the whole plane when placed at the origin. They are to be assigned to $n$ given locations (in arbitrary order, but without rotation) such that they still cover the whole plane. (This extends results of Bose et al. from 1997.) b) Convex partition: Partition a convex $m$-gon into $m$ convex parts, each part containing one of the edges and a given number of points from a given point set. (Garcia and Tejel 1995, Aurenhammer 2008)

Cite as

Günter Rote. Two Applications of Point Matching. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{rote:DagSemProc.09111.6,
  author =	{Rote, G\"{u}nter},
  title =	{{Two Applications of Point Matching}},
  booktitle =	{Computational Geometry},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.6},
  URN =		{urn:nbn:de:0030-drops-20292},
  doi =		{10.4230/DagSemProc.09111.6},
  annote =	{Keywords: Bipartite matching, least-squares}
}
Document
A Pseudopolynomial Algorithm for Alexandrov's Theorem

Authors: Daniel Kane, Gregory Nathan Price, and Erik Demaine

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)


Abstract
Alexandrov's Theorem states that every metric with the global topology and local geometry required of a convex polyhedron is in fact the intrinsic metric of some convex polyhedron. Recent work by Bobenko and Izmestiev describes a differential equation whose solution is the polyhedron corresponding to a given metric. We describe an algorithm based on this differential equation to compute the polyhedron given the metric, and prove a pseudopolynomial bound on its running time.

Cite as

Daniel Kane, Gregory Nathan Price, and Erik Demaine. A Pseudopolynomial Algorithm for Alexandrov's Theorem. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{kane_et_al:DagSemProc.09111.2,
  author =	{Kane, Daniel and Price, Gregory Nathan and Demaine, Erik},
  title =	{{A Pseudopolynomial Algorithm for Alexandrov's Theorem}},
  booktitle =	{Computational Geometry},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.2},
  URN =		{urn:nbn:de:0030-drops-20328},
  doi =		{10.4230/DagSemProc.09111.2},
  annote =	{Keywords: Folding, metrics, pseudopolynomial, algorithms}
}
Document
Minimizing Absolute Gaussian Curvature Locally

Authors: Joachim Giesen and Manjunath Madhusudan

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)


Abstract
One of the remaining challenges when reconstructing a surface from a finite sample is recovering non-smooth surface features like sharp edges. There is practical evidence showing that a two step approach could be an aid to this problem, namely, first computing a polyhedral reconstruction isotopic to the sampled surface, and secondly minimizing the absolute Gaussian curvature of this reconstruction globally. The first step ensures topological correctness and the second step improves the geometric accuracy of the reconstruction in the presence of sharp features without changing its topology. Unfortunately it is computationally hard to minimize the absolute Gaussian curvature globally. Hence we study a local variant of absolute Gaussian curvature minimization problem which is still meaningful in the context of surface fairing. Absolute Gaussian curvature like Gaussian curvature is concentrated at the vertices of a polyhedral surface embedded into $mathbb{R}^3$. Local optimization tries to move a single vertex in space such that the absolute Gaussian curvature at this vertex is minimized. We show that in general it is algebraically hard to find the optimal position of a vertex. By algebraically hard we mean that in general an optimal solution is not constructible, i.e., there exist no finite sequence of expressions starting with rational numbers, where each expression is either the sum, difference, product, quotient or $k$'th root of preceding expressions and the last expressions give the coordinates of an optimal solution. Hence the only option left is to approximate the optimal position. We provide an approximation scheme for the minimum possible value of the absolute Gaussian curvature at a vertex.

Cite as

Joachim Giesen and Manjunath Madhusudan. Minimizing Absolute Gaussian Curvature Locally. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{giesen_et_al:DagSemProc.09111.3,
  author =	{Giesen, Joachim and Madhusudan, Manjunath},
  title =	{{Minimizing Absolute Gaussian Curvature Locally}},
  booktitle =	{Computational Geometry},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.3},
  URN =		{urn:nbn:de:0030-drops-20311},
  doi =		{10.4230/DagSemProc.09111.3},
  annote =	{Keywords: Absolute Gaussian curvature, surface reconstruction, mesh smoothing}
}
Document
Open Problem Session

Authors: Joseph S. Mitchell

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)


Abstract
This is a scribing of the open problems posed at the Tuesday evening open problem session. Posers of problems provided input after the session.

Cite as

Joseph S. Mitchell. Open Problem Session. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{mitchell:DagSemProc.09111.4,
  author =	{Mitchell, Joseph S.},
  title =	{{Open Problem Session}},
  booktitle =	{Computational Geometry},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.4},
  URN =		{urn:nbn:de:0030-drops-20308},
  doi =		{10.4230/DagSemProc.09111.4},
  annote =	{Keywords: Open problems, computational geometry}
}
Document
Shortest Path Problems on a Polyhedral Surface

Authors: Carola Wenk and Atlas F. Cook

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)


Abstract
We develop algorithms to compute edge sequences, Voronoi diagrams, shortest path maps, the Fréchet distance, and the diameter for a polyhedral surface. Distances on the surface are measured either by the length of a Euclidean shortest path or by link distance. Our main result is a linear-factor speedup for computing all shortest path edge sequences on a convex polyhedral surface.

Cite as

Carola Wenk and Atlas F. Cook. Shortest Path Problems on a Polyhedral Surface. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{wenk_et_al:DagSemProc.09111.5,
  author =	{Wenk, Carola and Cook, Atlas F.},
  title =	{{Shortest Path Problems on a Polyhedral Surface}},
  booktitle =	{Computational Geometry},
  pages =	{1--30},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.5},
  URN =		{urn:nbn:de:0030-drops-20332},
  doi =		{10.4230/DagSemProc.09111.5},
  annote =	{Keywords: Shortest paths, edge sequences}
}
  • Refine by Author
  • 2 Agarwal, Pankaj K.
  • 2 Agarwal, Pankaj Kumar
  • 2 Sintos, Stavros
  • 2 Suri, Subhash
  • 2 Teillaud, Monique
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Absolute Gaussian curvature
  • 1 Algorithms
  • 1 Bipartite matching
  • 1 Euclidean shortest paths
  • 1 Folding
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 6 2009
  • 1 2011
  • 1 2017
  • 1 2018

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