19 Search Results for "Teillaud, Monique"

Document
DOI: 10.4230/LIPIcs.ESA.2024.29
A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels

Authors: Jean-Daniel Boissonnat and Kunal Dutta

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Computing persistent homology of large datasets using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, unlike in the case of persistent homology computation using the Euclidean distance or the k-distance, using Gaussian kernels involves significantly higher overhead, as all distance computations are in terms of the Gaussian kernel distance which is computationally more expensive. Further, most algorithmic implementations (e.g. Gudhi, Ripser, etc.) are based on Euclidean distances, so the question of finding a Euclidean embedding - preferably low-dimensional - that preserves the persistent homology computed with Gaussian kernels, is quite important. We consider the Gaussian kernel power distance (GKPD) given by Phillips, Wang and Zheng. Given an n-point dataset and a relative error parameter {ε} ∈ (0,1], we show that the persistent homology of the {Čech } filtration of the dataset computed using the GKPD can be approximately preserved using O({ε}^{-2}log n) dimensions, under a high stable rank condition. Our results also extend to the Delaunay filtration and the (simpler) case of the weighted Rips filtrations constructed using the GKPD. Compared to the Euclidean embedding for the Gaussian kernel function in ∼ n dimensions, which uses the Cholesky decomposition of the matrix of the kernel function applied to all pairs of data points, our embedding may also be viewed as dimensionality reduction - reducing the dimensionality from n to ∼ log n dimensions. Our proof utilizes the embedding of Chen and Phillips [ALT 2017], based on the Random Fourier Functions of Rahimi and Recht [NeurIPS 2007], together with two novel ingredients. The first one is a new decomposition of the squared radii of {Čech } simplices computed using the GKPD, in terms of the pairwise GKPDs between the vertices, which we state and prove. The second is a new concentration inequality for sums of cosine functions of Gaussian random vectors, which we call Gaussian cosine chaoses. We believe these are of independent interest and will find other applications in future.
Cite as

Jean-Daniel Boissonnat and Kunal Dutta. A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.ESA.2024.29,
  author =	{Boissonnat, Jean-Daniel and Dutta, Kunal},
  title =	{{A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.29},
  URN =		{urn:nbn:de:0030-drops-211009},
  doi =		{10.4230/LIPIcs.ESA.2024.29},
  annote =	{Keywords: Persistent homology, Gaussian kernels, Random Fourier Features, Euclidean embedding}
}
Document
DOI: 10.4230/LIPIcs.COSIT.2024.8
Scalable Harmonious Simplification of Isolines

Authors: Steven van den Broek, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
Isolines visually characterize scalar fields by connecting all points of the same value by a closed curve at repeated intervals. They work only as a set which gives the viewer an indication of the shape of the underlying field. Hence, when simplifying isolines it is important that the correspondence - the harmony - between adjacent isolines is preserved whenever it is present. The majority of state-of-the-art simplification methods treat isolines independently; at best they avoid collisions between adjacent simplified isolines. A notable exception is the work by Van Goethem et al. (2021) who were the first to introduce the concept of harmony between adjacent isolines explicitly as an algorithmic design principle. They presented a proof-of-concept algorithm that harmoniously simplifies a sequence of polylines. However, the sets of isolines of scalar fields, most notably terrain, consist of closed curves which are nested in arbitrarily complex ways and not of an ordered sequence of polylines. In this paper we significantly extend the work by Van Goethem et al. (2021) to capture harmony in general sets of isolines. Our new simplification algorithm can handle sets of isolines describing arbitrary scalar fields and is more efficient, allowing us to harmoniously simplify terrain with hundreds of thousands of vertices. We experimentally compare our method to the results of Van Goethem et al. (2021) on bundles of isolines and to general simplification methods on isolines extracted from DEMs of Antartica. Our results indicate that our method efficiently preserves the harmony in the simplified maps, which are thereby less noisy, cartographically more meaningful, and easier to read.
Cite as

Steven van den Broek, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann. Scalable Harmonious Simplification of Isolines. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vandenbroek_et_al:LIPIcs.COSIT.2024.8,
  author =	{van den Broek, Steven and Meulemans, Wouter and Reimer, Andreas and Speckmann, Bettina},
  title =	{{Scalable Harmonious Simplification of Isolines}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.8},
  URN =		{urn:nbn:de:0030-drops-208230},
  doi =		{10.4230/LIPIcs.COSIT.2024.8},
  annote =	{Keywords: Simplification, isolines, harmony}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.27
Computing a Dirichlet Domain for a Hyperbolic Surface

Authors: Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
This paper exhibits and analyzes an algorithm that takes a given closed orientable hyperbolic surface and outputs an explicit Dirichlet domain. The input is a fundamental polygon with side pairings. While grounded in topological considerations, the algorithm makes key use of the geometry of the surface. We introduce data structures that reflect this interplay between geometry and topology and show that the algorithm runs in polynomial time, in terms of the initial perimeter and the genus of the surface.
Cite as

Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud. Computing a Dirichlet Domain for a Hyperbolic Surface. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{despre_et_al:LIPIcs.SoCG.2023.27,
  author =	{Despr\'{e}, Vincent and Kolbe, Benedikt and Parlier, Hugo and Teillaud, Monique},
  title =	{{Computing a Dirichlet Domain for a Hyperbolic Surface}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.27},
  URN =		{urn:nbn:de:0030-drops-178771},
  doi =		{10.4230/LIPIcs.SoCG.2023.27},
  annote =	{Keywords: Hyperbolic geometry, Topology, Voronoi diagram, Algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.31
Minimal Delaunay Triangulations of Hyperbolic Surfaces

Authors: Matthijs Ebbens, Hugo Parlier, and Gert Vegter

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Motivated by recent work on Delaunay triangulations of hyperbolic surfaces, we consider the minimal number of vertices of such triangulations. First, we show that every hyperbolic surface of genus g has a simplicial Delaunay triangulation with O(g) vertices, where edges are given by distance paths. Then, we construct a class of hyperbolic surfaces for which the order of this bound is optimal. Finally, to give a general lower bound, we show that the Ω(√g) lower bound for the number of vertices of a simplicial triangulation of a topological surface of genus g is tight for hyperbolic surfaces as well.
Cite as

Matthijs Ebbens, Hugo Parlier, and Gert Vegter. Minimal Delaunay Triangulations of Hyperbolic Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ebbens_et_al:LIPIcs.SoCG.2021.31,
  author =	{Ebbens, Matthijs and Parlier, Hugo and Vegter, Gert},
  title =	{{Minimal Delaunay Triangulations of Hyperbolic Surfaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.31},
  URN =		{urn:nbn:de:0030-drops-138305},
  doi =		{10.4230/LIPIcs.SoCG.2021.31},
  annote =	{Keywords: Delaunay triangulations, hyperbolic surfaces, metric graph embeddings, moduli spaces}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.75
Generalizing CGAL Periodic Delaunay Triangulations

Authors: Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity.
Cite as

Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud. Generalizing CGAL Periodic Delaunay Triangulations. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 75:1-75:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{osang_et_al:LIPIcs.ESA.2020.75,
  author =	{Osang, Georg and Rouxel-Labb\'{e}, Mael and Teillaud, Monique},
  title =	{{Generalizing CGAL Periodic Delaunay Triangulations}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{75:1--75:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.75},
  URN =		{urn:nbn:de:0030-drops-129419},
  doi =		{10.4230/LIPIcs.ESA.2020.75},
  annote =	{Keywords: Delaunay triangulation, lattice, algorithm, software, experiments}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.35
Flipping Geometric Triangulations on Hyperbolic Surfaces

Authors: Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We consider geometric triangulations of surfaces, i.e., triangulations whose edges can be realized by disjoint geodesic segments. We prove that the flip graph of geometric triangulations with fixed vertices of a flat torus or a closed hyperbolic surface is connected. We give upper bounds on the number of edge flips that are necessary to transform any geometric triangulation on such a surface into a Delaunay triangulation.
Cite as

Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Flipping Geometric Triangulations on Hyperbolic Surfaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{despre_et_al:LIPIcs.SoCG.2020.35,
  author =	{Despr\'{e}, Vincent and Schlenker, Jean-Marc and Teillaud, Monique},
  title =	{{Flipping Geometric Triangulations on Hyperbolic Surfaces}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.35},
  URN =		{urn:nbn:de:0030-drops-121939},
  doi =		{10.4230/LIPIcs.SoCG.2020.35},
  annote =	{Keywords: Hyperbolic surface, Topology, Delaunay triangulation, Algorithm, Flip graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.44
Implementing Delaunay Triangulations of the Bolza Surface

Authors: Iordan Iordanov and Monique Teillaud

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The CGAL library offers software packages to compute Delaunay triangulations of the (flat) torus of genus one in two and three dimensions. To the best of our knowledge, there is no available software for the simplest possible extension, i.e., the Bolza surface, a hyperbolic manifold homeomorphic to a torus of genus two. In this paper, we present an implementation based on the theoretical results and the incremental algorithm proposed last year at SoCG by Bogdanov, Teillaud, and Vegter. We describe the representation of the triangulation, we detail the different steps of the algorithm, we study predicates, and report experimental results.
Cite as

Iordan Iordanov and Monique Teillaud. Implementing Delaunay Triangulations of the Bolza Surface. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{iordanov_et_al:LIPIcs.SoCG.2017.44,
  author =	{Iordanov, Iordan and Teillaud, Monique},
  title =	{{Implementing Delaunay Triangulations of the Bolza Surface}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.44},
  URN =		{urn:nbn:de:0030-drops-72173},
  doi =		{10.4230/LIPIcs.SoCG.2017.44},
  annote =	{Keywords: hyperbolic surface, Fuchsian group, arithmetic issues, Dehn's algorithm, CGAL}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.20
Delaunay Triangulations on Orientable Surfaces of Low Genus

Authors: Mikhail Bogdanov, Monique Teillaud, and Gert Vegter

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

Abstract
Earlier work on Delaunay triangulation of point sets on the 2D flat torus, which is locally isometric to the Euclidean plane, was based on lifting the point set to a locally isometric 9-sheeted covering space of the torus. Under mild conditions the Delaunay triangulation of the lifted point set, consisting of 9 copies of the input set, projects to the Delaunay triangulation of the input set. We improve and generalize this work. First we present a new construction based on an 8-sheeted covering space, which shows that eight copies suffice for the standard flat torus. Then we generalize this construction to the context of compact orientable surfaces of higher genus, which are locally isometric to the hyperbolic plane. We investigate more thoroughly the Bolza surface, homeomorphic to a sphere with two handles, both because it is the hyperbolic surface with lowest genus, and because triangulations on the Bolza surface have applications in various fields such as neuromathematics and cosmological models. While the general properties (existence results of appropriate covering spaces) show similarities with the results for the flat case, explicit constructions and their proofs are much more complex, even in the case of the apparently simple Bolza surface. One of the main reasons is the fact that two hyperbolic translations do not commute in general. To the best of our knowledge, the results in this paper are the first ones of this kind. The interest of our contribution lies not only in the results, but most of all in the construction of covering spaces itself and the study of their properties.
Cite as

Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay Triangulations on Orientable Surfaces of Low Genus. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.SoCG.2016.20,
  author =	{Bogdanov, Mikhail and Teillaud, Monique and Vegter, Gert},
  title =	{{Delaunay Triangulations on Orientable Surfaces of Low Genus}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{20:1--20:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.20},
  URN =		{urn:nbn:de:0030-drops-59129},
  doi =		{10.4230/LIPIcs.SoCG.2016.20},
  annote =	{Keywords: covering spaces, hyperbolic surfaces, finitely presented groups, Fuchsian groups, systole}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.33
Qualitative Symbolic Perturbation

Authors: Olivier Devillers, Menelaos Karavelas, and Monique Teillaud

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

Abstract
In a classical Symbolic Perturbation scheme, degeneracies are handled by substituting some polynomials in epsilon for the inputs of a predicate. Instead of a single perturbation, we propose to use a sequence of (simpler) perturbations. Moreover, we look at their effects geometrically instead of algebraically; this allows us to tackle cases that were not tractable with the classical algebraic approach.
Cite as

Olivier Devillers, Menelaos Karavelas, and Monique Teillaud. Qualitative Symbolic Perturbation. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{devillers_et_al:LIPIcs.SoCG.2016.33,
  author =	{Devillers, Olivier and Karavelas, Menelaos and Teillaud, Monique},
  title =	{{Qualitative Symbolic Perturbation}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{33:1--33:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.33},
  URN =		{urn:nbn:de:0030-drops-59259},
  doi =		{10.4230/LIPIcs.SoCG.2016.33},
  annote =	{Keywords: Robustness issues, Symbolic perturbations, Apollonius diagram}
}
Document
DOI: 10.4230/DagRep.5.3.41
Computational Geometry (Dagstuhl Seminar 15111)

Authors: Otfried Cheong, Jeff Erickson, and Monique Teillaud

Published in: Dagstuhl Reports, Volume 5, Issue 3 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15111 "Computational Geometry". The seminar was held from 8th to 13th March 2015 and 41 senior and young researchers from various countries and continents attended it. Recent developments in the field were presented and new challenges in computational geometry were identified.
Cite as

Otfried Cheong, Jeff Erickson, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 15111). In Dagstuhl Reports, Volume 5, Issue 3, pp. 41-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{cheong_et_al:DagRep.5.3.41,
  author =	{Cheong, Otfried and Erickson, Jeff and Teillaud, Monique},
  title =	{{Computational Geometry (Dagstuhl Seminar 15111)}},
  pages =	{41--62},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{3},
  editor =	{Cheong, Otfried and Erickson, Jeff and Teillaud, Monique},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.3.41},
  URN =		{urn:nbn:de:0030-drops-52689},
  doi =		{10.4230/DagRep.5.3.41},
  annote =	{Keywords: Algorithms, geometry, theory, approximation, implementation, combinatorics, topology}
}
Document
DOI: 10.4230/DagRep.3.4.34
Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151)

Authors: Stephen G. Kobourov, Martin Nöllenburg, and Monique Teillaud

Published in: Dagstuhl Reports, Volume 3, Issue 4 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13151 "Drawing Graphs and Maps with Curves". The seminar brought together 34 researchers from different areas such as graph drawing, information visualization, computational geometry, and cartography. During the seminar we started with seven overview talks on the use of curves in the different communities represented in the seminar. Abstracts of these talks are collected in this report. Six working groups formed around open research problems related to the seminar topic and we report about their findings. Finally, the seminar was accompanied by the art exhibition Bending Reality: Where Arc and Science Meet with 40 exhibits contributed by the seminar participants.
Cite as

Stephen G. Kobourov, Martin Nöllenburg, and Monique Teillaud. Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151). In Dagstuhl Reports, Volume 3, Issue 4, pp. 34-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{kobourov_et_al:DagRep.3.4.34,
  author =	{Kobourov, Stephen G. and N\"{o}llenburg, Martin and Teillaud, Monique},
  title =	{{Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151)}},
  pages =	{34--68},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{4},
  editor =	{Kobourov, Stephen G. and N\"{o}llenburg, Martin and Teillaud, Monique},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.4.34},
  URN =		{urn:nbn:de:0030-drops-41680},
  doi =		{10.4230/DagRep.3.4.34},
  annote =	{Keywords: graph drawing, information visualization, computational cartography, computational geometry}
}
Document
DOI: 10.4230/DagRep.3.3.1
Computational Geometry (Dagstuhl Seminar 13101)

Authors: Otfried Cheong, Kurt Mehlhorn, and Monique Teillaud

Published in: Dagstuhl Reports, Volume 3, Issue 3 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13101 "Computational Geometry". The seminar was held from 3rd to 8th March 2013 and 47 senior and young researchers from various countries and continents attended it. Recent developments in the field were presented and new challenges in computational geometry were identified. This report collects abstracts of the talks and a list of open problems.
Cite as

Otfried Cheong, Kurt Mehlhorn, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 13101). In Dagstuhl Reports, Volume 3, Issue 3, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{cheong_et_al:DagRep.3.3.1,
  author =	{Cheong, Otfried and Mehlhorn, Kurt and Teillaud, Monique},
  title =	{{Computational Geometry (Dagstuhl Seminar 13101)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{3},
  editor =	{Cheong, Otfried and Mehlhorn, Kurt and Teillaud, Monique},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.3.1},
  URN =		{urn:nbn:de:0030-drops-40210},
  doi =		{10.4230/DagRep.3.3.1},
  annote =	{Keywords: Algorithms, geometry, theory, approximation, implementation, combinatorics, topology}
}
Document
DOI: 10.4230/DagRep.1.3.19
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.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
DOI: 10.4230/DagSemProc.09111.1
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.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
DOI: 10.4230/DagSemProc.09111.6
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.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}
}
  • Refine by Author
  • 11 Teillaud, Monique
  • 2 Agarwal, Pankaj Kumar
  • 2 Cheong, Otfried
  • 2 Despré, Vincent
  • 2 Mehlhorn, Kurt
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Computational geometry
  • 3 Mathematics of computing → Geometric topology
  • 1 Information systems → Geographic information systems
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graphs and surfaces
  • Show More...

  • Refine by Keyword
  • 3 Algorithms
  • 3 combinatorics
  • 3 geometry
  • 3 implementation
  • 3 theory
  • Show More...

  • Refine by Type
  • 19 document

  • Refine by Publication Year
  • 6 2009
  • 2 2013
  • 2 2016
  • 2 2020
  • 2 2024
  • Show More...

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