1 Search Results for "Singh, Nitin"


Document
Efficient Algorithms to Decide Tightness

Authors: Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)


Abstract
Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but more efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of 3-manifolds - a problem which previously was thought to be hard. In addition, for the more difficult problem of deciding tightness of 4-dimensional combinatorial manifolds, we describe an algorithm that is fixed parameter tractable in the treewidth of the 1-skeletons of the vertex links. Finally, we show that simpler treewidth parameters are not viable: for all non-trivial inputs, we show that the treewidths of both the 1-skeleton and the dual graph must grow too quickly for a standard treewidth-based algorithm to remain tractable.

Cite as

Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer. Efficient Algorithms to Decide Tightness. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bagchi_et_al:LIPIcs.SoCG.2016.12,
  author =	{Bagchi, Bhaskar and Datta, Basudeb and Burton, Benjamin A. and Singh, Nitin and Spreer, Jonathan},
  title =	{{Efficient Algorithms to Decide Tightness}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.12},
  URN =		{urn:nbn:de:0030-drops-59040},
  doi =		{10.4230/LIPIcs.SoCG.2016.12},
  annote =	{Keywords: discrete geometry and topology, polynomial time algorithms, fixed parameter tractability, tight triangulations, simplicial complexes}
}
  • Refine by Author
  • 1 Bagchi, Bhaskar
  • 1 Burton, Benjamin A.
  • 1 Datta, Basudeb
  • 1 Singh, Nitin
  • 1 Spreer, Jonathan

  • Refine by Classification

  • Refine by Keyword
  • 1 discrete geometry and topology
  • 1 fixed parameter tractability
  • 1 polynomial time algorithms
  • 1 simplicial complexes
  • 1 tight triangulations

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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