Volume

Dagstuhl Seminar Proceedings, Volume 9111

Publication Details

  • published at: 2009-06-23
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.09111.1
09111 Abstracts Collection – Computational Geometry

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

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
DOI: 10.4230/DagSemProc.09111.2
A Pseudopolynomial Algorithm for Alexandrov's Theorem

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

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
DOI: 10.4230/DagSemProc.09111.3
Minimizing Absolute Gaussian Curvature Locally

Authors: Joachim Giesen and Manjunath Madhusudan

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
DOI: 10.4230/DagSemProc.09111.4
Open Problem Session

Authors: Joseph S. Mitchell

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
DOI: 10.4230/DagSemProc.09111.5
Shortest Path Problems on a Polyhedral Surface

Authors: Carola Wenk and Atlas F. Cook

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}
}
Document
DOI: 10.4230/DagSemProc.09111.6
Two Applications of Point Matching

Authors: Günter Rote

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}
}

Filters

  • Authors
  • A
  • Agarwal, Pankaj Kumar
  • Alt, Helmut
  • C
  • Cook, Atlas F.
  • D
  • Demaine, Erik
  • G
  • Giesen, Joachim
  • K
  • Kane, Daniel
  • M
  • Madhusudan, Manjunath
  • Mitchell, Joseph S.
  • P
  • Price, Gregory Nathan
  • R
  • Rote, Günter
  • T
  • Teillaud, Monique
  • W
  • Wenk, Carola

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