Search

Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths in portalgons. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons., Comment: 34 pages. Full version of a paper to appear in a shorter form in the 39th International Symposium on Computational Geometry (SoCG 2023)

In this thesis we introduce a new discretization of the Gaussian curvature on piecewise flat surfaces. It is defined on the conical singularities of the surface and it is the quotient of the angle defect and the area of the Voronoi cell. We investigate the existence and uniqueness of metrics with constant discrete Gaussian curvature within discrete conformal classes of piecewise flat surfaces. Two piecewise flat surfaces with a fixed triangulation are discrete conformally equivalent if there exists a conformal factor u i at each vertex i of the triangulation, such that the lengths of each edge ij with respect to the two piecewise linear metrics are related by the factors at the vertices. However, this notion is not suitable for proofs of existence and uniqueness, since it relies on fixed combinatorics. We use a generalization of this notion, based on hyperbolic geometry. We derive several variational principles and prove that every discrete conformal class possesses a piecewise linear metric with constant discrete Gaussian curvature. Although many notions are defined for euclidean triangular meshes, we show that our method is in fact independent of the choice of triangulation and is thus well-defined for piecewise flat surfaces. To tackle the question of uniqueness we conduct a thorough analysis of discrete conformal classes of a fixed genus and number of vertices. We prove that uniqueness holds for spheres with three marked points and surfaces of genus larger than zero with one marked point. We provide explicit counterexamples for uniqueness by analyzing the discrete conformal classes of spheres with four marked points and surfaces of genus two with two marked points., In dieser Arbeit führen wir eine neue Diskretisierung der Gaußschen Krümmung auf stückweise flachen Flächen ein. Diese Krümmung ist definiert als der Quotient des Winkeldefekts und des Flächeninhalts der Voronoizelle. Wir untersuchen die Existenz und Eindeutigkeit von Metriken konstanter diskreter Gaußscher Krümmung in den diskreten konformen Klassen von stückweise flachen Flächen. Zwei stückweise flache Flächen mit einer festen Triangulierung sind diskret konform äquivalent, falls an jeder Ecke i der Triangulierung ein konformer Faktor u_i existiert, so dass die Längen jeder Kante ij bezüglich der stückweise linearen Metriken in einer bestimmten Beziehung stehen. Dieser Begriff ist jedoch nicht für Existenz- und Eindeutigkeitsbeweise geeignet, da er sich auf eine feste Kombinatorik bezieht. Wir benutzen eine Verallgemeinerung dieses Begriffs, die auf hyperbolischer Geometrie basiert. Wir leiten mehrere Variationsprinzipien her und zeigen, dass jede diskret konforme Klasse eine stückweise lineare Metrik mit konstanter diskreter Gaußscher Krümmung beinhaltet. Obwohl viele Begriffe für Euklidische Triangulierungen definiert sind, zeigen wir, dass unsere Methode unabhängig von der Wahl der Triangulierung ist. Daher ist sie auf stückweise flachen Flächen wohldefiniert. Zur Frage der Eindeutigkeit führen wir eine weitreichende Untersuchung der diskreten konformen Klassen auf Flächen vom festen Geschlecht und mit einer festen Anzahl an markierten Punkten durch. Wir beweisen, dass die Eindeutigkeit für Sphären mit drei markierten Punkten und Flächen vom Geschlecht größer als Null mit einem markierten Punkt gilt. Wir konstruieren Gegenbeispiele in den diskreten konformen Klassen auf der Sphäre mit vier markierten Punkten und der Fläche vom Geschlecht zwei mit zwei markierten Punkten um zu zeigen, dass die Eindeutigkeit im Allgemeinen nicht gilt.

3D printers use 3D models in the form of meshes to define the geometry and the appearance of objects to be printed. A 3D mesh must have some topological properties so that the geometry it represents could be printable and the geometry itself must respect certain conditions to be printable. These properties and conditions may vary depending on the 3D printing technologies in use.Many 3D meshes used for printing were not initially designed for this purpose application. The main primary use of these meshes is visualization, which does not require the same topological properties and geometric conditions. The subject of this thesis is the repair of these meshes to make them printable.A repair chain including several steps was designed for this purpose. Non-manifold conditions are repaired by extracting related components (surfaces). The boundaries of surfaces are detected and classified according to the best repair to be applied on each. The boundaries of surfaces are repaired according to their classification either by a filling method or by an offset method. The weakness of the geometry is detected and controlled.; Les imprimantes 3D utilisent des modèles 3D sous la forme de maillages pour définir la géométrie et l'apparence des objets à imprimer. Un maillage 3D doit posséder certaines propriétés topologiques pour que la géométrie qu'il représente soit imprimable, et la géométrie elle même doit respecter certaines conditions pour être imprimable. Ces propriétés et conditions peuvent varier selon la technologie d'impression 3D utilisée.De nombreux maillages 3D utilisés pour l'impression n'ont dans un premier temps pas été conçus pour cette application. La principale utilisation première de ces maillages est la visualisation, qui ne nécessite pas les mêmes propriétés topologiques et conditions géométriques. Le sujet de cette thèse est la réparation de ces maillages afin de les rendre imprimables.Une chaîne de réparation comprenant plusieurs étapes a été conçue dans ce but. Les conditions de non-variété sont réparées en réalisant une extraction de composantes connexes (surfaces). Les bords des surfaces sont détectés et classés en fonction de la meilleure réparation à appliquer sur chaque. Les bords des surfaces sont réparés suivant leurs classement soit par une méthode de remplissage soit par une méthode d'épaississement. La fragilité de la géométrie est détectée et contrôlée.

We introduce a new discretization of the Gaussian curvature on piecewise at surfaces. As the prime new feature the curvature is scaled by the factor 1/r2 upon scaling the metric globally with the factor r. We develop a variational principle to tackle the corresponding discrete uniformisation theorem – we show that each piecewise at surface is discrete conformally equivalent to one with constant discrete Gaussian curvature. This surface is in general not unique. We demonstrate uniqueness for particular cases and disprove it in general by providing explicit counterexamples. Special attention is paid to dealing with change of combinatorics.

Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms which are both simple and efficient in theory and in practice. Randomized incremental constructions are usually space-optimal and time-optimal in the worst case, as exemplified by the construction of convex hulls, Delaunay triangulations, and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst case. For example, it is known that the Delaunay triangulation of nicely distributed points in $${\mathbb {E}}^d$$ E d or on polyhedral surfaces in $${\mathbb {E}}^3$$ E 3 has linear complexity, as opposed to a worst-case complexity of $$\Theta (n^{\lfloor d/2\rfloor })$$ Θ ( n ⌊ d / 2 ⌋ ) in the first case and quadratic in the second. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the two cases above and variants of them, the complexity of the usual RIC is $$O(n\log n)$$ O ( n log n ) , which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. At the heart of our proof is a bound on the complexity of the Delaunay triangulation of random subsets of $${\varepsilon }$$ ε -nets. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.

In der vorliegenden Arbeit untersuche ich die Diskretisierung glatter Fl��chen durch polyhedrale Fl��chen mit ebenen Facetten. Dabei soll die polyhedrale Fl��che hinsichtlich ihrer Knickenergie minimiert werden. Hierbei ist die Knickenergie definiert als die Summe ��ber alle Betr��ge der Winkel zwischen zwei angrenzenden Fl��chen, gewichtet mit der L��nge der jeweils gemeinsamen Kante. Dieser Term l��sst sich als diskrete Version einer totalen absoluten Kr��mmung interpretieren. L��sst man die Feinheit der Diskretisierung gegen Null gehen, so zeigt sich, dass ein Minimum der Knickenergie erreicht wird, wenn die Kanten entlang der Hauptkr��mmungslinien der glatten Fl��che verlaufen. Das l��sst die Schlussfolgerung zu, dass eine polyhedrale Fl��che mit minimaler Knickenergie aus ebenen Rechtecken bestehen sollte. Ein ��hnliches Problem mit einer isotropen Version der Knickenergie wurde bereits in Martin Kilian (2017) behandelt. Der isotrope Fall l��sst sich analog zum Volumenbeziehungsweise Kostenminimierungsproblem einer tragenden Struktur formulieren, wie es bei Michell (1904) auftritt. Die auftretenden Parallelen zwischen den Michell Strukturen und polyhedralen Fl��chen minimalen Knicks suggerieren, dass auch die Fl��chen minimalen Knicks physikalisch optimale Eigenschaften aufweisen., In this thesis we aim to represent smooth geometric shapes with polyhedral surfaces with planar faces. The polyhedral surface is optimized regarding the dihedral angle energy. Here the dihedral angle energy is defined as the sum of all absolute values of dihedral angles between adjacent faces weighted with the length of the common edge of the regarding faces. This energy term can be interpreted as a discrete version of a total absolute curvature. In the limit case of a subdivision process we find that the dihedral angle energy is minimal if the edges of the polyhedral surface follow the principal curvature lines of the underlying smooth surface. Instead of the euclidean dihedral energy one could also minimize the isotropic dihedral angle energy, where length and angle are replaced by isotropic length and isotropic angle. This has been done in Martin Kilian (2017) and will be examined in this thesis as well. The isotropic case can be formulated to match the minimization problem dealt with in Michell (1904), where a load bearing structure is optimized regarding its volume. The parallels between the minimal surfaces regarding isotropic dihedral angle energy, minimal surfaces regarding euclidean dihedral angle energy and Michell structures suggest that minimizing the dihedral angle energy not only leads to visually pleasing results but also gives physically optimized solutions.

3D printers use 3D models in the form of meshes to define the geometry and the appearance of objects to be printed. A 3D mesh must have some topological properties so that the geometry it represents could be printable and the geometry itself must respect certain conditions to be printable. These properties and conditions may vary depending on the 3D printing technologies in use.Many 3D meshes used for printing were not initially designed for this purpose application. The main primary use of these meshes is visualization, which does not require the same topological properties and geometric conditions. The subject of this thesis is the repair of these meshes to make them printable.A repair chain including several steps was designed for this purpose. Non-manifold conditions are repaired by extracting related components (surfaces). The boundaries of surfaces are detected and classified according to the best repair to be applied on each. The boundaries of surfaces are repaired according to their classification either by a filling method or by an offset method. The weakness of the geometry is detected and controlled., Les imprimantes 3D utilisent des modèles 3D sous la forme de maillages pour définir la géométrie et l'apparence des objets à imprimer. Un maillage 3D doit posséder certaines propriétés topologiques pour que la géométrie qu'il représente soit imprimable, et la géométrie elle même doit respecter certaines conditions pour être imprimable. Ces propriétés et conditions peuvent varier selon la technologie d'impression 3D utilisée.De nombreux maillages 3D utilisés pour l'impression n'ont dans un premier temps pas été conçus pour cette application. La principale utilisation première de ces maillages est la visualisation, qui ne nécessite pas les mêmes propriétés topologiques et conditions géométriques. Le sujet de cette thèse est la réparation de ces maillages afin de les rendre imprimables.Une chaîne de réparation comprenant plusieurs étapes a été conçue dans ce but. Les conditions de non-variété sont réparées en réalisant une extraction de composantes connexes (surfaces). Les bords des surfaces sont détectés et classés en fonction de la meilleure réparation à appliquer sur chaque. Les bords des surfaces sont réparés suivant leurs classement soit par une méthode de remplissage soit par une méthode d'épaississement. La fragilité de la géométrie est détectée et contrôlée.

We present a new graph-based method, called discrete geodesic graph (DGG), to compute discrete geodesics in a divide-and-conquer manner. Let M be a manifold triangle mesh with n vertices and >0 the given accuracy parameter. Assume the vertices are uniformly distributed on the input mesh. We show that the DGG associated to M has O(n) edges and the shortest path distances on the graph approximate geodesic distances on M with relative error O(). Computational results show that the actual error is less than 0.6 on common models. Taking advantage of DGG's unique features, we develop a DGG-tailored label-correcting algorithm that computes geodesic distances in empirically linear time. With DGG, we can guarantee the computed distances are true distance metrics, which is highly desired in many applications. We observe that DGG significantly outperforms saddle vertex graph (SVG) another graph based method for discrete geodesics in terms of graph size, accuracy control and runtime performance. A new graph-based method for computing geodesic distances on manifold triangle meshes.It allows user to directly specify the accuracy, and runs empirically linear time.It outperforms saddle vertex graph in terms of graph size, accuracy control and runtime performance.

Este trabalho se divide em quatro partes principais, no primeiro capítulo fazemos uma breve introdução. No segundo capítulo estudamos teoria básica de geometria e equações diferenciais, estudamos também geodésicas em superfícies no R3 baseados nos trabalhos de R. Garcia e J. Sotomayor em [10] e de W. Klingenberg em [15], estes fornecem um estudo rigoroso do comportamento das geodésicas no elipsóide. O terceiro capítulo é inspirado na famosa conjectura dada em em 1905 em seu artigo “Sur les lignes géodésiques des surfaces convexes” H. Poincaré fez uma pergunta sobre a existência de pelo menos três geodésicas simples fechadas sobre superfícies suaves convexas homeomorfas à esfera S2, neste capítulo estudamos esta conjectura em superfícies poliedrais baseado em [9] e os textos [1],[4]. No último tema de abordagem analisamos o comportamento de geodésicas em superfícies no espaço de Lorentz, focando nosso estudo no elipsóide, este estudo é baseado principalmente no livro de Tilla Weinstein [25] e no artigo [11] de S. Tabachnikov, Khesin e Genin. This work is divided in four parts, in the first chapter we give an introduction. In the next chapter we study basic theory of geometry and differential equations, we study some results of geodesics theory on surfaces in R3; based in the works of R. Garcia and J. Sotomayor in [10] and W. Klingenberg in [15]. These ones provide a study of the behavior of the geodesic in the ellipsoid. The third chapter is inspired by the famous question given in 1905, in his famous article “Sur les lignes géodésiques des surfaces convexes” H. Poincaré posed a question on the existence of at least three geometrically different closed geodesics without self-intersections on any smooth convex two-dimensional surface (2-surface) M homeomorphic to the two-dimensional sphere (2-sphere) S2. We study this question for convex polyhedral surfaces following the paper [9] by G. Galperin and the books [1],[4]. In the last topic we will address the behavior of geodesics on Lorentz surfaces, focusing our study on the ellipsoid based mainly on the book of Tilla Weinstein [25] and in the paper [11] by S. Tabachnikov, Khesin and Genin. Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq

The goal of the course is to introduce some of the recent developments on discrete conformal geometry of polyhedral surfaces. We plan to cover the following topics.- The Andreev-Koebe-Thurston theorem on circle packing polyhedral metrics and Marden-Rodin’s proof- Thurston’s conjecture on the convergence of circle packings to the Riemann mapping and its solution by Rodin-Sullivan- Finite dimensional variational principles associated to polyhedral surfaces- A discrete conformal equivalence of polyhedral surfaces and its relationship to convex polyhedra in hyperbolic 3-space- A discrete uniformization theorem for compact polyhedral surfaces- Convergence of discrete conformality and some open problems

The goal of the course is to introduce some of the recent developments on discrete conformal geometry of polyhedral surfaces. We plan to cover the following topics.- The Andreev-Koebe-Thurston theorem on circle packing polyhedral metrics and Marden-Rodin’s proof- Thurston’s conjecture on the convergence of circle packings to the Riemann mapping and its solution by Rodin-Sullivan- Finite dimensional variational principles associated to polyhedral surfaces- A discrete conformal equivalence of polyhedral surfaces and its relationship to convex polyhedra in hyperbolic 3-space- A discrete uniformization theorem for compact polyhedral surfaces- Convergence of discrete conformality and some open problems

Our recent joint work with D. Gu established a discrete version of the uniformization theorem for compact polyhedral surfaces. In this talk, we prove that discrete uniformizaton maps converge to conformal maps when the triangulations are sufficiently fine chosen. We will also discuss the relationship between the discrete uniformization theorem and convex polyhedral surfaces in the hyperbolic 3-space. This is a joint work with J. Sun and T. Wu.

The goal of the course is to introduce some of the recent developments on discrete conformal geometry of polyhedral surfaces. We plan to cover the following topics.- The Andreev-Koebe-Thurston theorem on circle packing polyhedral metrics and Marden-Rodin’s proof- Thurston’s conjecture on the convergence of circle packings to the Riemann mapping and its solution by Rodin-Sullivan- Finite dimensional variational principles associated to polyhedral surfaces- A discrete conformal equivalence of polyhedral surfaces and its relationship to convex polyhedra in hyperbolic 3-space- A discrete uniformization theorem for compact polyhedral surfaces- Convergence of discrete conformality and some open problems

The goal of the course is to introduce some of the recent developments on discrete conformal geometry of polyhedral surfaces. We plan to cover the following topics.- The Andreev-Koebe-Thurston theorem on circle packing polyhedral metrics and Marden-Rodin’s proof- Thurston’s conjecture on the convergence of circle packings to the Riemann mapping and its solution by Rodin-Sullivan- Finite dimensional variational principles associated to polyhedral surfaces- A discrete conformal equivalence of polyhedral surfaces and its relationship to convex polyhedra in hyperbolic 3-space- A discrete uniformization theorem for compact polyhedral surfaces- Convergence of discrete conformality and some open problems

We investigate necessary conditions for the existence of projections of polytopes that preserve full k-skeleta. More precisely, given the combinatorics of a polytope and the dimension e of the target space, what are obstructions to the existence of a geometric realization of a polytope with the given combinatorial type such that a linear projection to e-space strictly preserves the k-skeleton. Building on the work of Sanyal (2009), we develop a general framework to calculate obstructions to the existence of such realizations using topological combinatorics. Our obstructions take the form of graph colorings and linear integer programs. We focus on polytopes of product type and calculate the obstructions for products of polygons, products of simplices, and wedge products of polytopes. Our results show the limitations of constructions for the deformed products of polygons of Sanyal & Ziegler (2009) and the wedge product surfaces of R��rig & Ziegler (2009) and complement their results., 18 pages, 2 figures

This survey gives a brief overview of theoretically and practically relevant algorithms to compute geodesic paths and distances on three-dimensional surfaces. The survey focuses on three-dimensional polyhedral surfaces. The goal of this survey is to identify the most relevant open problems, both theoretical and practical.

We study discrete curvatures computed from nets of curvature lines on a given smooth surface, and prove their uniform convergence to smooth principal curvatures. We provide explicit error bounds, with constants depending only on properties of the smooth limit surface and the shape regularity of the discrete net., Comment: 21 pages, 8 figures