TY - THES A1 - Graf, Simone T1 - Kamerakalibrierung mit radialer Verzeichnung – die radiale essentielle Matrix T1 - Camera Calibration with Radial Distortion - the Radial Essential Matrix N2 - In der Bildverarbeitung wird die beobachtende Kamera meist als Lochkamera modelliert: ein Modell, das zahlreiche theoretische Vorteile bietet. So kann etwa das Abbildungsverhalten als projektive Abbildung aufgefasst werden. In einem Stereokamerasystem dieses Modells stehen korrespondierende Punkte – das sind Bildpunkte desselben 3D-Punktes – in einem linearen Zusammenhang, der auch ohne Kenntnis der Kameraparameter aus beobachteten Korrespondenzen geschätzt werden kann. Für die meisten Kameras, insbesondere für solche mit Weitwinkelobjektiven, ist die Modellannahme einer Lochkamera allerdings sichtbar unzureichend. Deshalb müssen zusätzlich zur Lochkamera noch Verzeichnungsabbildungen ins Modell integriert werden. In dieser Arbeit wird gezeigt, dass bei polynomialer radialer Verzeichnung die Parameter der Projektionsabbildung die Verzeichnungsparameter bestimmen. Dieses theoretische Ergebnis fließt in Algorithmen zur Kamerakalibrierung, d.h. zur Bestimmung der Parameter eines Kameramodells, ein. Diese wurden experimentell getestet und mit bestehenden Verfahren verglichen. Weiterhin wird die radiale essentielle Matrix eingeführt, die die Beziehung von korrespondierenden Punkten im Stereokamerafall bei radialer Verzeichnung beschreibt. Es werden vier Algorithmen vorgestellt, die diese theoretische Beziehung verwerten. Sie geben an, wie aus korrespondierenden Punkten die radiale essentielle Matrix geschätzt werden kann und welche Kameraparameter daraus gewonnen werden können. Damit ist beispielsweise eine Nachkalibrierung möglich. Auch diese Verfahren wurden implementiert und evaluiert. Umgekehrt ist bei bekannter radialer essentieller Matrix eine Einschränkung des Suchraums für korrespondierende Punkte möglich, die für die Rekonstruktion benötigt werden. KW - Optische Messtechnik KW - Kalibrieren KW - Stereokamera KW - Kamera KW - Korrespondenzproblem KW - Bildverarbeitung KW - Bildkorrelatio KW - Kamerakalibrierung KW - radiale Verzeichnung KW - epipolare Einschränkung KW - camera calibration KW - radial distortion KW - epipolar constraint Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-12711 ER - TY - INPR A1 - Kreitmeier, Wolfgang A1 - Linder, Tamas T1 - High-Resolution Scalar Quantization with Rényi Entropy Constraint N2 - We consider optimal scalar quantization with $r$th power distortion and constrained R\'enyi entropy of order $\alpha$. For sources with absolutely continuous distributions the high rate asymptotics of the quantizer distortion has long been known for $\alpha=0$ (fixed-rate quantization) and $\alpha=1$ (entropy-constrained quantization). These results have recently been extended to quantization with R\'enyi entropy constraint of order $\alpha \ge r+1$. Here we consider the more challenging case $\alpha\in [-\infty,0)\cup (0,1)$ and for a large class of absolutely continuous source distributions we determine the sharp asymptotics of the optimal quantization distortion. The achievability proof is based on finding (asymptotically) optimal quantizers via the companding approach, and is thus constructive. KW - Maßtheorie KW - Quantisierung KW - Entropie KW - Companding KW - high-resolution asymptotics KW - optimal quantization KW - Rényi entropy Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-23787 N1 - This is a preprint of an article accepted for publication in the IEEE Transactions on Information Theory Journal, ISSN: 0018-9448. The original publication is available at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 ER - TY - INPR A1 - Kreitmeier, Wolfgang T1 - Optimal quantization for the one-dimensional uniform distribution with Rényi -α-entropy constraints N2 - We establish the optimal quantization problem for probabilities under constrained Rényi-α-entropy of the quantizers. We determine the optimal quantizers and the optimal quantization error of one-dimensional uniform distributions including the known special cases α = 0 (restricted codebook size) and α = 1 (restricted Shannon entropy). KW - Maßtheorie KW - Quantisierung KW - Entropie KW - optimal quantization KW - uniform distribution KW - Rényi-α-entropy Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-16983 ER - TY - THES A1 - Kreitmeier, Wolfgang T1 - Optimale Quantisierung verallgemeinerter Cantor-Verteilungen N2 - Für verallgemeinerte Cantor-Verteilungen, die im Eindimensionalen mittels klassischer Wischkonstruktion bzw. in höheren Dimensionen über iterierte Funktionensysteme definiert werden, wird das Problem der optimalen Quantisierung unter bestimmten Voraussetzungen vollständig gelöst. Es werden die optimalen Codebücher bestimmt und Formeln für den optimalen Quantisierungsfehler bewiesen. Im eindimensionalen Fall wird eine Existenzcharakterisierung der Quantisierungsdimension gegeben und unter bestimmten Voraussetzungen die Nichtexistenz des Quantisierungskoeffizienten gezeigt. Auch in höheren Dimensionen wird für die betrachteten Verteilungen bewiesen, dass der Quantisierungskoeffizient, bei existenter Quantisierungsdimension, nicht existiert. Die gewonnenen Resultate werden auf die Gleichverteilungen von modifizierten klassischen fraktalen Mengen, wie das Sierpinski-Dreieck, die Cantormenge und den Cantor-Staub angewandt. KW - Maßtheorie KW - Fraktale Dimension KW - Iteriertes Funktionensystem KW - Sierpinski-Menge KW - Cantor-Menge KW - Hausdorff-Dimension KW - Hausdorff-Maß KW - Optimale Quantisierung KW - homogene Cantormaße KW - Quantisierungsdimension KW - Quantisierungskoeffizient KW - Sierpinski-Dreieck KW - Optimal Quantization KW - homogeneous Cantor measures KW - Quantization dimension KW - Quantization coefficient KW - Sierpinski Gasket Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-913 ER - TY - THES A1 - Lauren, Verena T1 - Semilineare Approximation in der Bildrekonstruktion N2 - In der Bildverarbeitung spielen Segmentierungsalgorithmen, bei denen die Art der zu segmentierenden Menge schon im Voraus festgelegt werden kann und nur noch ihre Größe und Lage angepasst werden muss, eine eher untergeordnete Rolle. Gründe hierfür sind vor allem komplizierte Zielfunktionen und daraus resultierende lange Rechenzeiten, die zudem meist kein optimales Ergebnis liefern. Dabei kann eine mengenbasierte Segmentierung durchaus sinnvoll eingesetzt werden, wenn gewisse Rahmenbedingungen eingehalten werden. In dieser Arbeit wird eine Theorie zur allgemeinen mengenbasierten Segmentierung vorgestellt und untersucht, unter welchen Bedingungen optimale Segmentierungsergebnisse erreicht werden können. Die anschließenden Anwendungen bestätigen die Nützlichkeit dieser Theorie. KW - Optimale Rekonstruktion KW - Rekonstruktion KW - Bildverarbeitung KW - Objektrekonstruktion KW - Bildrekonstruktion KW - image reconstruction KW - image processing KW - object reconstruction Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-730 ER - TY - INPR A1 - Kreitmeier, Wolfgang A1 - Linder, Tamas T1 - Entropy Density and Mismatch in High-Rate Scalar Quantization with Rényi Entropy Constraint N2 - Properties of scalar quantization with $r$th power distortion and constrained R\'enyi entropy of order $\alpha\in (0,1)$ are investigated. For an asymptotically (high-rate) optimal sequence of quantizers, the contribution to the R\'enyi entropy due to source values in a fixed interval is identified in terms of the "entropy density" of the quantizer sequence. This extends results related to the well-known point density concept in optimal fixed-rate quantization. A dual of the entropy density result quantifies the distortion contribution of a given interval to the overall distortion. The distortion loss resulting from a mismatch of source densities in the design of an asymptotically optimal sequence of quantizers is also determined. This extends Bucklew's fixed-rate ($\alpha=0$) and Gray \emph{et al.}'s variable-rate ($\alpha=1$)mismatch results to general values of the entropy order parameter $\alpha$ KW - Maßtheorie KW - Quantisierung KW - Entropie KW - Asymptotic quantization theory KW - distortion density KW - entropy density KW - quantizer mismatch KW - Rényi-entropy Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-26132 N1 - This is a preprint of an article accepted for publication in the IEEE Transactions on Information Theory Journal, ISSN: 0018-9448. The original publication is available at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=18 ER - TY - THES A1 - Bachl, Walter T1 - Interaktives orthogonales Zeichnen von planaren Graphen N2 - Die Arbeit beschäftigt sich mit dem automatischen Zeichnen von Graphen. Hier wird ein interaktiver Ansatz untersucht, bei dem der Graph mit einer Menge von Operationen Schritt für Schritt aufgebaut wird. Der Zielgraph und die Einfügereihenfolge sind dabei nicht fest vorgegeben, sondern werden vom Benutzer bestimmt. In der Arbeit wird vor allem ein Szenario für zweifach zusammenhängende Graphen untersucht und ein für diese Zwecke passendes Zeichenmodell entwickelt. Dieser Ansatz wird dann um verschiedene Varianten erweitert. Außerdem wird gezeigt, dass das flächenminimale Zeichnen in dem neu entwickelten Zeichenmodell NP-vollständig ist. KW - Graphenzeichnen KW - Graphalgorithmen KW - Flächenminimales Zeichnen Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus-392 ER - TY - THES A1 - Lorenz, Florian T1 - Analyse und Erzeugung von glatten Flächenübergängen für das CNC-Fräsen N2 - In dieser Arbeit werden numerisch stabile Methoden zur Prüfung von Stetigkeiten an Flächenübergängen vorgestellt und Algorithmen zur Erzeugung von G^2-stetigen Flächenübergängen hergeleitet. KW - Differentialgeometrie KW - B-Spline KW - Geometrische Modellierung KW - CNC-Maschine Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-5166 ER - TY - THES A1 - Apfler, Sabine T1 - Erwerb mathematischer Kompetenzen in der Regelvolksschule N2 - Durch die Einführung der Bildungsstandardsüberprüfungen erhält die Frage nach der Kompetenzentwicklung von Kindern einen zentralen Stellenwert in Bildungsangelegenheiten. Lehrkräfte stehen dadurch vor der Aufgabe, ihren Unterricht diesbezüglich zu verändern und Lösungen zu finden. Die Frage, ob der Einsatz der Montessoripädagogik die Entwicklung mathematischer Kompetenzen positiv beeinflusst, wurde im Rahmen einer Dissertation diskutiert und empirisch erforscht werden. Der Arbeit liegt folgende Fragestellung zugrunde: Kann die Montessoripädagogik dazu beitragen, dass Schülerinnen und Schüler in österreichischen Regelvolksschulen ein hohes Kompetenzniveau in Mathematik erreichen? Wie unterscheidet sich die Kompetenzentwicklung in Klassen, die von Lehrpersonen mit beziehungsweise ohne Montessoriausbildung unterrichtet werden? Bei der vorliegenden Studie handelt es sich um eine Längsschnittuntersuchung mit zwei Testzeitpunkten. Im Sinne einer summativen Evaluation wurden zu Beginn der Untersuchung die Basiskompetenzen mit dem „Entwicklungsorientierten Test zur Erfassung mathematischer Basiskompetenzen ab Schuleintritt (MBK 1+)“ analysiert. Am Ende der dritten Schulstufe wurde eine abschließende Bewertung im Rahmen der IKM-Testung des BIFIE vorgenommen, um die Wirksamkeit des Einsatzes der Montessorimethode zu ermitteln. Untersucht wurden 14 Volksschulklassen, die entweder einer Untersuchungsgruppe oder einer Kontrollgruppe zugeordnet wurden. Die Klassen der Untersuchungsgruppe wurden von Lehrpersonen mit Montessori-Diplomausbildung unterrichtet, die Klassen der Kontrollgruppe von Lehrpersonen, die keine Montessoriausbildung absolviert haben. An der Studie nahmen 248 Schülerinnen und Schüler teil. Der Untersuchungszeitraum erstreckte sich über insgesamt drei Schuljahre. Die Ergebnisse der Studie zeigen Tendenzen, dass sich der Einsatz der Montessoripädagogik positiv auf die Kompetenzentwicklung der Kinder im Bereich der Mathematik auswirkt. KW - Montessori KW - Mathematik KW - Kompetenzen KW - Österreich KW - Regelschule KW - Mathematikunterricht KW - Montessori-Pädagogik KW - Längsschnittuntersuchung Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-5593 ER - TY - THES A1 - Stadler, Thomas T1 - Eine Anwendung der Invariantentheorie auf das Korrespondenzproblem lokaler Bildmerkmale N2 - Als sich in der ersten Hälfte des 19. Jahrhunderts zunehmend mehr bedeutende Mathematiker mit der Suche nach Invarianten beschäftigten, konnte natürlich noch niemand vorhersehen, dass die Invariantentheorie mit Beginn des Computerzeitalters in der Bildverarbeitung bzw. dem Rechnersehen ein äußerst fruchtbares Anwendungsgebiet finden wird. In dieser Arbeit wird eine neue Anwendungsmöglichkeit der Invariantentheorie in der Bildverarbeitung vorgestellt. Dazu werden lokale Bildmerkmale betrachtet. Dabei handelt es sich um die Koordinaten einer Polynomfunktion bzgl. einer geeigneten Orthonormalbasis von P_n(R^2,R), die die zeitintegrierte Sensorinputfunktion auf lokalen Pixelfenstern bestmöglich approximiert. Diese Bildmerkmale werden in vielen Anwendungen eingesetzt, um Objekte in Bildern zu erkennen und zu lokalisieren. Beispiele hierfür sind die Detektion von Werkstücken an einem Fließband oder die Verfolgung von Fahrbahnmarkierungen in Fahrerassistenzsystemen. Modellieren lässt sich die Suche nach einem Muster in einem Suchbild als Paar von Stereobildern, auf denen lokal die affin-lineare Gruppe AGL(R) operiert. Will man also feststellen, ob zwei lokale Pixelfenster in etwa Bilder eines bestimmten dreidimensionalen Oberflächenausschnitts sind, ist zu klären, ob die Bildausschnitte durch eine Operation der Gruppe AGL(R) näherungsweise ineinander übergeführt werden können. Je nach Anwendung genügt es bereits, passende Untergruppen G von AGL(R) zu betrachten. Dank der lokalen Approximation durch Polynomfunktionen induziert die Operation einer Untergruppe G eine Operation auf dem reellen Vektorraum P_n(R^2,R). Damit lässt sich das Korrespondenzproblem auf die Frage reduzieren, ob es eine Transformation T in G gibt so, dass p ungefähr mit der Komposition von q und T für die zugehörigen Approximationspolynome p,q in P_n(R^2,R) gilt. Mit anderen Worten, es ist zu klären, ob sich p und q näherungsweise in einer G-Bahn befinden, eine typische Fragestellung der Invariantentheorie. Da nur lokale Bildausschnitte betrachtet werden, genügt es weiter, Untergruppen G von GL_2(R) zu betrachten. Dann erhält man sofort auch die Antwort für das semidirekte Produkt von R^2 mit G. Besonders interessant für Anwendungen ist hierbei die spezielle orthogonale Gruppe G=SO_2(R) und damit insgesamt die eigentliche Euklidische Gruppe. Für diese Gruppe und spezielle Pixelfenster ist das Korrespondenzproblem bereits gelöst. In dieser Arbeit wird das Problem in eben dieser Konstellation ebenfalls gelöst, allerdings auf elegante Weise mit Methoden der Invariantentheorie. Der Ansatz, der hier vorgestellt wird, ist aber nicht auf diese Gruppe und spezielle Pixelfenster begrenzt, sondern leicht auf weitere Fälle erweiterbar. Dazu ist insbesondere zu klären, wie sich sogenannte fundamentale Invarianten von lokalen Bildmerkmalen, also letztendlich Invarianten von Polynomfunktionen, berechnen lassen, d.h. Erzeugendensysteme der entsprechenden Invariantenringe. Mit deren Hilfe lässt sich die Zugehörigkeit einer Polynomfunktion zur Bahn einer anderen Funktion auf einfache Weise untersuchen. Neben der Vorstellung des Verfahrens zur Korrespondenzfindung und der dafür notwendigen Theorie werden in dieser Arbeit Erzeugendensysteme von Invariantenringen untersucht, die besonders "schöne" Eigenschaften besitzen. Diese schönen Erzeugendensysteme von Unteralgebren werden, analog zu Gröbner-Basen als Erzeugendensysteme von Idealen, SAGBI-Basen genannt ("Subalgebra Analogs to Gröbner Bases for Ideals"). SAGBI-Basen werden hier insbesondere aus algorithmischer Sicht behandelt, d.h. die Berechnung von SAGBI-Basen steht im Vordergrund. Dazu werden verschiedene Algorithmen erarbeitet, deren Korrektheit bewiesen und implementiert. Daraus resultiert ein Software-Paket zu SAGBI-Basen für das Computeralgebrasystem ApCoCoA, dessen Funktionalität in diesem Umfang in keinem Computeralgebrasystem zu finden sein wird. Im Zuge der Umsetzung der einzelnen Algorithmen konnte außerdem die Theorie der SAGBI-Basen an zahlreichen Stellen erweitert werden. KW - Computeralgebra KW - SAGBI-Basen KW - Invariantentheorie KW - Bildverarbeitung KW - (lokale) Bildmerkmale Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-4026 ER - TY - THES A1 - Handeck, Jörg T1 - Analyse und Korrektur von Teileprogrammen für numerisch gesteuerte Werkzeugmaschinen N2 - Splinekurven sind oft das erste Mittel der Wahl, wenn Daten interpoliert oder approximiert werden sollen. Sie spielen in vielen praktischen Anwendungsbereichen eine wichtige Rolle und sind in Bereichen des CAD/CAM nicht mehr weg zu denken. In der vorliegenden Arbeit werden in diesem Kontext Bahnpunkte zur Steuerung von Werkzeugmaschinen untersucht. Die Analyse wird mit Hilfe eines Multiresolution (MRA) Ansatzes für Splinekurven mit adaptiven Knotenfolgen realisiert. Dieser MRA Ansatz basiert auf einer Least-Squares-Projektion zum Knotenentfernen und unterscheidet sich somit zu bekannten Ansätzen, die auf orthogonalen Komplementen aufbauen. Des Weiteren wird ein Konzept zur Approximation von Orientierungsdaten mittels homogenen Quaternionensplines vorgestellt. Diese Splines leben auf der Sphäre und lassen sich mittels Knotenentfernen bzw. einfügen verfeinern. Somit lässt sich das vorgestellte MRA–Analyseverfahren ebenfalls auf diese Kurven anwenden. Weiter konnte für diese Kurven eine konvexe Hülle–Eigenschaft nachgewiesen werden. KW - Spline MRA KW - Spline KW - Numerische Steuerung KW - Werkzeugmaschine Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-4546 ER - TY - THES A1 - Pfeffer, Wolfgang T1 - Qualitative Entwicklung der Begriffsbildung im Fach Mathematik in der Studieneingangsphase N2 - Der Übergang vom sekundären zum tertiären Bildungsbereich im Fach Mathematik stellt in den vergangenen Jahren ein zentrales Forschungsinteresse der mathematikdidaktischen Forschung dar. Das Forschungsfeld macht hierbei drei grundlegende Bedingungsfaktoren aus: epistemologische und kognitive, soziologische und kulturelle sowie didaktische Schwierigkeiten. Der Schwerpunkt der vorliegenden Arbeit liegt auf dem ersten Bereich, der den sich wandelnden Charakter der Mathematik inkludiert. Für viele Studienanfängerinnen und -anfänger ist der Wechsel von der Schule zur Universität "traumatisch", da sich das Anforderungsprofil an der Hochschule doch deutlich von dem bisher Gewohnten abhebt. Gerade die Studieneingangsphase ist für den späteren Studienerfolg als wichtigster Abschnitt anzusehen; werden die vielfach vorhandenen fachlichen Defizite sowie falschen Vorstellungen nicht beseitigt, führt dies oft zu einem vorzeitigen Studienabbruch. Untersuchungen zur mathematischen Begriffsbildung über einen längeren Zeitraum im Verlauf eines Hochschulstudiums fehlen bislang. Hieraus ergibt sich die Motivation für das in dieser Arbeit beschriebene Forschungsprojekt, das sich in drei Teile gliedert. Der erste Teil fasst den Stand der Forschung zum Übergang Schule -- Hochschule im Fach Mathematik zusammen. Der Fokus richtet sich dabei auf den sich wandelnden Charakter der Mathematik sowie die unterschiedlichen Anforderungen in Bezug auf die Begriffsbildung. Der zweite Teil stellt mathematisches Vorwissen als möglichen Bedingungsfaktor für den Studienerfolg dar und beschreibt anschließend Konzeption, Auswertung sowie die Diskussion der Ergebnisse eines Fragebogens zum Hintergrundwissen Mathematik. Der dritte Teil der Arbeit beschreibt eine qualitative und längsschnittlich durchgeführte, leitfadengestützte Interviewstudie, in deren Rahmen die gleiche Stichprobe im Laufe der ersten beiden Semester zu drei unterschiedlichen Zeitpunkten befragt wurde. Im Hinblick auf die praktische Relevanz für die Lehre wurden anhand der Äußerungen der Studierenden Fehlvorstellungen hinsichtlich der mathematischen Konzepte identifiziert und kategorisiert. Weiter wird eine Klassifikation der studentischen Vorstellungen hinsichtlich deren wissenschaftlichen Qualität vorgenommen sowie die Entwicklung dieser über die drei Interviewzeitpunkte hinweg beschrieben. Die Ergebnisse der Arbeit zeigen einerseits massive Defizite der Studienanfängerinnen und -anfänger in Kenntnissen und Fertigkeiten mathematischen Grundwissens. Darüber hinaus erfolgt auch die Begriffsbildung resp. -entwicklung hinsichtlich zentraler mathematischer Konzepte der Hochschulmathematik auf sehr niedrigem Niveau. Als Indiz hierfür zeugen die vielfältig identifizierten Fehlvorstellungen, die sich über alle Interviewzeitpunkte hinweg zeigten. Hieraus resultiert eine verstärkte Notwendigkeit der Förderung der Begriffsbildung sowie -entwicklung in der Studieneingangsphase. KW - Übergang Schule - Hochschule KW - Concept Image KW - Concept Definition KW - Begriffsbildung KW - Kognitives Schema KW - Mathematikstudium KW - Studienanfang Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-4948 ER - TY - THES A1 - Gütschow, Silja T1 - Roulets - Eine Integraltransformation zur Bestimmung gerichteter Singularitäten N2 - In dieser Arbeit wird eine neue Integraltransformation, die Roulettransformation, eingeführt. Diese arbeitet mit anisotropen Skalierungen und Rotationen. Es wird gezeigt, dass die Roulettransformation allgemeine gerichtete Singularitäten im Sinne von temperierten Distributionen auflöst. Die Abklingraten an Punkt- sowie Liniensingularitäten werden explizit angegeben. KW - Integraltransformation KW - Singularität Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-5929 ER - TY - THES A1 - Brummer, Stephan T1 - Numerisch robuste Berechnung der zirkulären Sichtbarkeitsmenge N2 - Sichtbarkeitsprobleme, wie das Folgende, gehören zu den grundlegenden Problemen der algorithmischen Geometrie: Berechne zu einem einfachen Polygon, dem sogenannten Kanal, und zu einem darin enthaltenen Punkt die von diesem Punkt aus sichtbare Punktmenge. Dabei ist ein Punkt von einem anderen Punkt aus sichtbar, wenn deren Verbindungsstrecke den Kanal nicht verlässt. Wir wollen uns in dieser Arbeit mit zirkulärer Sichtbarkeit beschäftigen. Zur Verbindung zweier Punkte sind dann nicht nur Strecken, sondern auch Kreisbögen zulässig. Außerdem betrachten wir als Ausgangspunkt dieser sogenannten Sichtbarkeitskreisbögen und -strecken eine Kante des Kanals anstatt eines einzelnen Punkts. Konkret liefert diese Arbeit einen Beitrag zur numerisch robusten Bestimmung der zirkulären Sichtbarkeitsmenge ausgehend von einer Kante des Kanals. Hierfür wird in dieser Arbeit ein Algorithmus vorgestellt, mit dem für einen gegebenen Punkt festgestellt werden kann, ob dieser von der Startkante aus sichtbar ist. Im Fall eines sichtbaren Punkts wird ein Sichtbarkeitskreisbogen berechnet, der zwei Kanalberührungen besitzt. Damit kann der Algorithmus bei geeigneter Wahl des zu untersuchenden Punkts – der als dritte Kanalberührung fungiert – direkt zur Berechnung von sogenannten Grenzkreisbögen der Sichtbarkeitsmenge benutzt werden. Diese definieren den Rand der zirkulären Sichtbarkeitsmenge und zeichnen sich dadurch aus, dass sie vom Kanal dreimal abwechselnd von links und von rechts berührt werden. Der beschriebene Algorithmus basiert auf der Untersuchung derjenigen Kreisbögen, die zwar nicht notwendigerweise vollständig im Kanal liegen, aber die Startkante mit dem Punkt verbinden, dessen Sichtbarkeit bestimmt werden soll. Insbesondere werden dabei die Bereiche untersucht, in denen der jeweilige Kreisbogen den Kanal verlässt, die sogenannten Verletzungen. Da die „Schwere“ einer solchen Verletzung quantifizierbar ist, wird ein iteratives Vorgehen ermöglicht. Dabei wird der Kreisbogen iterativ so verändert, dass dieser bei gleichem Endpunkt den Kanal immer „weniger verlässt“. Ist der Endpunkt und damit der zu untersuchende Punkt nicht sichtbar, wird im Laufe des Algorithmus festgestellt, dass keine derartige Verbesserung möglich ist. Der vorgestellte Algorithmus ist numerisch robust, einfach umzusetzen und besitzt eine in der Anzahl der Kanalecken lineare Laufzeit. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-12299 ER - TY - THES A1 - Neuwirth, Daniel T1 - Einbettung und Charakterisierung von aligned bar 1-visibility Graphen und outer fan free Graphen N2 - In dieser Arbeit werden drei verschiedene Klassen von Graphen untersucht. Die Klassen sind die bar (1;1)-visibilty Graphen, die aligned bar 1-visibility Graphen und die outer fan free Graphen. Die Klassen werden durch ihre möglichen Einbettungen charakterisiert. Die Repräsentation der bar (1; j)-visibility Graphen ist, dass jeder Knoten als horizontaler Strich und jede Kante als vertikaler Strich gezeichnet wird. Eine Kante kann einen Knoten genau einmal schneiden und ein Knoten kann j-mal geschnitten werden. Wir erweitern die Ergebnisse von Dean et. al. und geben Beispiele mit einer maximalen Dichte an für bar (1; 2)-visibility, bar (1; 3)-visibility und bar (1; 4)-visibility Graphen und geben einen maximal dünnen Graphen für die Klasse der bar (1;1) visibility Graphen an. Wir zeigen, dass die Klassen der bar (1; j)-visibility Graphen für 1 < j < 1eine unendliche Hierarchie bilden. Abschließend beweisen wir, dass das Erkennungsproblem ob ein Graph eine bar (1;1)-visibility Repräsentation hat, NP-vollständig ist. Die Klasse der aligned bar 1-visibility Graphen (AB1V ) erhält man, indem man die bar (1;1)-visibility Repräsentation um 90 Grad dreht und alle Knoten verlängert, so dass diese alle mit der y-Koordinate 0 starten. Die relative Position bzgl. der x-Koordinate wird mit der t-Ordnung beschrieben und mit der r-Ordnung die relative Position bzgl. der y-Koordinate. Wir erweitern die Erkenntnisse von Felsner und Massow für die Klasse der AB1V Graphen bzgl. ihrer maximalen Dichte, der minimale Grad eines Knotens. Wir führen die Methode Pfadaddition ein, um anhand deren Abschlusseigenschaften zu unterscheiden, ob ein Graph in einer Klasse liegt oder nicht. Diese Methode nutzen wir, um die Beziehung der Klasse der AB1V Graphen mit anderen Klassen zu untersuchen. Für die Klasse der maximalen Graphen geben wir einen dünnen Graphen und eine untere Schranke bzgl. der Dichte an. Wir geben einen Algorithmus an, welcher eine Bucheinbettung aus einer AB1V Einbettung berechnet. Für die Klassen der optimalen AB1V Graphen geben wir einen Einbettungsalgorithmus an. Wir verbessern den Erkennungsalgorithmus von Felsner und Massow, ob ein Graph mit einer gegebenen t-Ordnung eine AB1V Einbettung besitzt. Für die Klasse der distinkt strong AB1V Graphen, Graphen in der jeder Knoten ein unterschiedliche r-Ordnung hat und maximal für die r-Ordnung ist, geben wir einen Algorithmus an, der in O(n6) eine mögliche Einbettung berechnet. Zum Schluss zeigen wir für diese Klasse, dass es exponentiell viele verschiedene Einbettungen gibt. Ein Graph hat eine outer fan free Einbettung, wenn alle Knoten inzident zu einer Fläche sind und keine Kante von zwei Kanten geschnitten wird, die adjazent zu einem Knoten sind. Wir untersuchen diese Klasse zuerst auf die Dichte. Weiter erforschen wir die Beziehung zwischen den Klassen der AB1V , RAC und k-planaren Graphen. Abschließend geben wir eine Reduktion von NAE-3-SAT auf das Erkennungsproblem von outer fan free Graphen an. KW - Graph Drawing Y1 - 2026 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19930 ER -