Search

Realization problems are a recurrent theme in Discrete Geometry. The generic realization problem can be phrased as follows: „Is there an object living in Euclidean space Rd that satisfies some given conditions?“ The most straightforward way to give a solution of such a problem is the construction of an object with the desired properties. For non-realizability the straightforward approach is complete enumeration of all possible objects and showing for each one of them that it doesn't meet the conditions given. In theory this often is possible because the discrete setting reduces to a finite number of combinatorial possibilities. However, the number of possibilities typically grows exponentially with the size of the object and thus makes this approach intractable very quickly. Therefore indirect methods and conceptual arguments are pursued. One method is to expose an „obstruction“ to realizability, i.e. a property all realizable instances have and that contradicts the given conditions. In Chapter 1 we takle a problem for point configurations in the Euclidean plane. Starting from ideas of Ungar and of Pach, Pinchasi and Sharir we present two algorithms that find in a given point configuration sets of segments which are non-parallel and primitive or non- avoiding respectively. Then we turn our attention to the Jamison-Hill catalogue of slope-critical examples which have the minimal possible number of non-parallel segments. Among these we find three examples where the two conditions listed above cannot be met simultaneously. In the other examples of the catalogue we give complete systems of non-avoiding primitive segments. In Chapter 2 we construct a family of special deformed d-cubes. To this end we streamline an approach of Ziegler and Rörig. For every dimension d >= 4 we get a cube Cd that has an increasing Hamiltonian path with respect to the last coordinate xd. At the same time Cd contains the quadrilateral surface Fd on 2d vertices constructed by McMullen, Schulz and Wills (1985) in its 2-skeleton in such a way that Fd survives the projection to the last three coordinates. The starting point for Chapter 3 is Stratified Morse Theory (SMT) as developed by Goresky and MacPherson. For polyhedral complexes in Rd and especially for polyhedral surfaces in R3 the Morse data can be obtained in a purely combinatorial way once a vertex ordering is fixed. Afterwards we go beyond pure SMT for surfaces and do a more detailed analysis of possible forms of critical points. In Chapter 4 we follow the approach of Novik that exploits the classical obstruction theory for piecewise linear embeddability to find „obstruction systems“ for geometric realizability. We associate with any simplicial complex K and any integer m a system of linear equations and inequalities. If K has a simplicial embedding in Rm then the system has an integer solution. This extends the work of Novik by using not only intersection but also linking numbers., Realisierungsprobleme treten in der diskreten Geometrie an den veschiedensten Stellen auf. Die allgemeine Fragestellung ist dabei, ob es ein Objekt im Anschauungsraum gibt, dass vorgegebene kombinatorische Bedingungen erfüllt. Der direkte Weg, diese Frage zu beantworten, ist, ein Objekt mit den geforderten Eigenschaften zu konstruieren. Für Nicht-Realisierbarkeit ist der direkte Weg eine vollständige Aufzählung aller möglichen Objekte und der Nachweis, dass keines davon die kombinatorischen Bedingungen erfüllt. Theoretisch ist das oft möglich, da die diskrete Fragestellung nur endlich viele kombinatorische Möglichkeiten zulässt. In der Praxis scheitert dieser Ansatz an der exponentiell mit der Größe des Objekts wachsenden Anzahl an Möglichkeiten. Daher braucht man alternative Methoden, um Nicht- Realisierbarkeit nachzuweisen. In Kapitel 1 befassen wir uns mit einer Fragestellung über Punktkonfigurationen in der Ebene. Aus Ideen von Ungar einerseits und Pach, Pinchasi und Sharir andererseits entwickeln wir zwei Algorithmen, die für eine gegebene Punktkonfiguration Teilmengen der Verbindungsstrecken finden, die nicht parallel und zusätzlich primitiv oder nicht-vermeidend sind. Danach untersuchen wir den Katalog von Jamison und Hill, der alle bekannten Punktkonfigurationen enthält, die die minimale Anzahl verschiedener Steigungen definieren. Unter diesen finden wir drei Beispiele, in denen es keine Teilmenge von Verbindungsstrecken gibt, die gleichzeitig alle Richtungen repräsentieren, nicht-vermeidend und primitiv sind. In Kapitel 2 konstruieren wir eine Familie deformierter d-dimensionaler Würfel. Für jede Dimension d >= 4 erhalten wir einen Würfel Cd, der einen aufsteigenden Hamiltonpfad bezüglich der letzten Koordinate xd hat. Gleichzeitig enthält Cd die Flächen Fd auf 2d Ecken von McMullen, Schulz und Wills im 2-Skelett derart, dass Fd die Projektion auf die letzten drei Koordinaten übersteht. Dazu benutzen wir Ansätze von Ziegler und Rörig. Der Ausgangspunkt für Kapitel 3 ist die von Goresky und MacPherson entwickelte Stratifizierte Morse Theorie (SMT). Für polyedrische Komplexe in Rd zeigen wir, dass die Morsedaten nur aus der Eckenreihenfolge und den kombinatorischen Daten gewonnen werden können. Anschließend gehen wir für polyedrische Flächen im R3 über die reine SMT hinaus und untersuchen genauer, wie kritische Punkte aussehen können und welche Effekte sie haben. In Kapitel 4 folgen wir einem Ansatz von Novik, der die klassische Hindernistheorie für stückweise lineare Einbettbarkeit nutzt, um „Hindernissysteme'“ für geometrische Realisierbarkeit anzugeben. Wir konstruieren zu einem gegebenen Simplizialkomplex K und ganzzahliges m ein System linearer Gleichungen und Ungleichungen. Wenn K eine simpliziale Einbettung in Rm hat, dann hat das System eine ganzzahlige Lösung. Die Bedingungen bei Novik rühren von Schnittzahlen her. In dieser Arbeit beschreiben wir, wie wir zusätzliche Bedingungen aus Verschlingungszahlen erhalten.

We show a remarkable fact about folding paper: from a single rectangular sheet of paper, one can fold it into a flat origami that takes the (scaled) shape of any connected polygonal region, even if it has holes. This resolves a long-standing open problem in origami design. Our proof is constructive, utilizing tools of computational geometry, resulting in efficient algorithms for achieving the target silhouette. We show further that if the paper has a different color on each side, we can form any connected polygonal pattern of two colors. Our results apply also to polyhedral surfaces, showing that any polyhedron can be “wrapped” by folding a strip of paper around it. We give three methods for solving these problems: the first uses a thin strip whose area is arbitrarily close to optimal; the second allows wider strips to be used; and the third varies the strip width to optimize the number or length of visible “seams” subject to some restrictions.

The high level of realism and interaction in many computer graphic applications requires techniques for processing complex geometric models. First, we present a method that provides an accurate low-resolution approximation from a multi-chart textured model that guarantees geometric fidelity and correct preservation of the appearance attributes. Then, we introduce a mesh structure called Compact Model that approximates dense triangular meshes while preserving sharp features, allowing adaptive reconstructions and supporting textured models. Next, we design a new space deformation technique called *Cages based on a multi-level system of cages that preserves the smoothness of the mesh between neighbouring cages and is extremely versatile, allowing the use of heterogeneous sets of coordinates and different levels of deformation. Finally, we propose a hybrid method that allows to apply any deformation technique on large models obtaining high quality results with a reduced memory footprint and a high performance., L’elevat nivell de realisme i d’interacció requerit en múltiples aplicacions gràfiques fa que siguin necessàries tècniques pel processament de models geomètrics complexes. En primer lloc, presentem un mètode de simplificació que proporciona una aproximació precisa de baixa resolució d'un model texturat que garanteix fidelitat geomètrica i una correcta preservació de l’aparença. A continuació, introduïm el Compact Model, una nova estructura de dades que permet aproximar malles triangulars denses preservant els trets més distintius del model, permetent reconstruccions adaptatives i suportant models texturats. Seguidament, hem dissenyat *Cages, un esquema de deformació basat en un sistema de caixes multi-nivell que conserva la suavitat de la malla entre caixes veïnes i és extremadament versàtil, permetent l'ús de conjunts heterogenis de coordenades i diferents nivells de deformació. Finalment, proposem un mètode híbrid que permet aplicar qualsevol tècnica de deformació sobre models complexes obtenint resultats d’alta qualitat amb una memòria reduïda i un alt rendiment.

Let V be a finite point set in 3D and let ST(V ) be the set of closed triangulated polyhedral surfaces with a vertex set V. Those surfaces can be dened as 2:5D (closed) triangulations of the given discrete data set V. We generalise the operation of diagonal flip for 2:5D triangulations by omitting the usual restriction that the flip operation should not produce a self-intersecting triangulation. We denote this flip operation by EDF (extended diagonal flip). Among all possible 2:5D triangulations with the vertex set V we first single out those that are topologically equivalent to the 2D sphere. We show that any two such 2:5D triangulations (if V is situated in general position), are equivalent under EDF, i.e., they can be transformed into each other via a finite sequence of EDF.

Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in these applications begin by constructing the three-dimensional Delaunay triangulation of a finite set of points scattered over a surface. Their running-time therefore depends on the complexity of the Delaunay triangulation of such point sets. Although the Delaunay triangulation of points in ^3 can be quadratic in the worst-case, we show that, under some mild sampling condition, the complexity of the 3D Delaunay triangulation of points distributed on a fixed number of facets of ^3 (e.g. the facets of a polyhedron) is linear. Our bound is deterministic and the constants are explicitly given.

It is well known that the complexity of the Delaunay triangulation of $n$ points in $R ^d$, i.e. the number of its simplices, can be $\Omega (n^\lceil \frac{d{2}\rceil })$. In particular, in $R ^3$, the number of tetrahedra can be quadratic. Differently, if the points are uniformly distributed in a cube or a ball, the expected complexity of the Delaunay triangulation is only linear. The case of points distributed on a surface is of great practical importance in reverse engineering since most surface reconstruction algorithms first construct the Delaunay triangulation of a set of points measured on a surface. In this paper, we bound the complexity of the Delaunay triangulation of points distributed on the boundary of a given polyhedron. Under a mild uniform sampling condition, we provide deterministic asymptotic bounds on the complexity of the 3D Delaunay triangula- tion of the points when the sampling density increases. More precisely, we show that the complexity is $O(n^1.8)$ for general polyhedral surfaces and $O(n\sqrtn)$ for convex polyhedral surfaces. Our proof uses a geometric result of independent interest that states that the medial axis of a surface is well approximated by a subset of the Voronoi vertices of the sample points. The proof extends easily to higher dimensions, leading to the first non trivial bounds for the problem when $d>3$.

We show how the theory of deformations of geometric structures (development and holonomy) applied to the case of piecewise flat surfaces leads to some interesting geometric structures on the moduli space of a punctured surface.