3 Search Results for "Bjerkevik, Håvard Bakke"


Document
Tighter Bounds for Reconstruction from ε-Samples

Authors: Håvard Bakke Bjerkevik

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
We show that reconstructing a curve in ℝ^d for d ≥ 2 from a 0.66-sample is always possible using an algorithm similar to the classical NN-Crust algorithm. Previously, this was only known to be possible for 0.47-samples in ℝ² and 1/3-samples in ℝ^d for d ≥ 3. In addition, we show that there is not always a unique way to reconstruct a curve from a 0.72-sample; this was previously only known for 1-samples. We also extend this non-uniqueness result to hypersurfaces in all higher dimensions.

Cite as

Håvard Bakke Bjerkevik. Tighter Bounds for Reconstruction from ε-Samples. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bakkebjerkevik:LIPIcs.SoCG.2022.9,
  author =	{Bakke Bjerkevik, H\r{a}vard},
  title =	{{Tighter Bounds for Reconstruction from \epsilon-Samples}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.9},
  URN =		{urn:nbn:de:0030-drops-160170},
  doi =		{10.4230/LIPIcs.SoCG.2022.9},
  annote =	{Keywords: Curve reconstruction, surface reconstruction, \epsilon-sampling}
}
Document
Quasi-Universality of Reeb Graph Distances

Authors: Ulrich Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
We establish bi-Lipschitz bounds certifying quasi-universality (universality up to a constant factor) for various distances between Reeb graphs: the interleaving distance, the functional distortion distance, and the functional contortion distance. The definition of the latter distance is a novel contribution, and for the special case of contour trees we also prove strict universality of this distance. Furthermore, we prove that for the special case of merge trees the functional contortion distance coincides with the interleaving distance, yielding universality of all four distances in this case.

Cite as

Ulrich Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr. Quasi-Universality of Reeb Graph Distances. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2022.14,
  author =	{Bauer, Ulrich and Bjerkevik, H\r{a}vard Bakke and Fluhr, Benedikt},
  title =	{{Quasi-Universality of Reeb Graph Distances}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.14},
  URN =		{urn:nbn:de:0030-drops-160221},
  doi =		{10.4230/LIPIcs.SoCG.2022.14},
  annote =	{Keywords: Reeb graphs, contour trees, merge trees, distances, universality, interleaving distance, functional distortion distance, functional contortion distance}
}
Document
Computational Complexity of the Interleaving Distance

Authors: Håvard Bakke Bjerkevik and Magnus Bakke Botnan

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


Abstract
The interleaving distance is arguably the most prominent distance measure in topological data analysis. In this paper, we provide bounds on the computational complexity of determining the interleaving distance in several settings. We show that the interleaving distance is NP-hard to compute for persistence modules valued in the category of vector spaces. In the specific setting of multidimensional persistent homology we show that the problem is at least as hard as a matrix invertibility problem. Furthermore, this allows us to conclude that the interleaving distance of interval decomposable modules depends on the characteristic of the field. Persistence modules valued in the category of sets are also studied. As a corollary, we obtain that the isomorphism problem for Reeb graphs is graph isomorphism complete.

Cite as

Håvard Bakke Bjerkevik and Magnus Bakke Botnan. Computational Complexity of the Interleaving Distance. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bjerkevik_et_al:LIPIcs.SoCG.2018.13,
  author =	{Bjerkevik, H\r{a}vard Bakke and Botnan, Magnus Bakke},
  title =	{{Computational Complexity of the Interleaving Distance}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{13:1--13:15},
  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.13},
  URN =		{urn:nbn:de:0030-drops-87268},
  doi =		{10.4230/LIPIcs.SoCG.2018.13},
  annote =	{Keywords: Persistent Homology, Interleavings, NP-hard}
}
  • Refine by Author
  • 2 Bjerkevik, Håvard Bakke
  • 1 Bakke Bjerkevik, Håvard
  • 1 Bauer, Ulrich
  • 1 Botnan, Magnus Bakke
  • 1 Fluhr, Benedikt

  • Refine by Classification
  • 2 Mathematics of computing → Geometric topology
  • 1 Mathematics of computing → Trees
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Curve reconstruction
  • 1 Interleavings
  • 1 NP-hard
  • 1 Persistent Homology
  • 1 Reeb graphs
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2022
  • 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