37 Arbeiten
Diese Studie nutzt persistente Homologie auf einem gefilterten Zeugenkomplex, um Lücken in der Abdeckung von Kühlzentren zu identifizieren und vergleicht diese topologische Methode mit dem herkömmlichen Hitze-Verwundbarkeitsindex, um ein umfassenderes Verständnis der Hitzegefährdung in verschiedenen US-Städten zu ermöglichen.
Die Autoren stellen eine neue Subgradienten-Definition für Hadamard-Räume vor, die auf Busemann-Funktionen basiert und stochastische sowie inkrementelle Subgradientenverfahren mit garantierten Komplexitätsgrenzen für konvexe Optimierungsprobleme wie die Berechnung von Medians im BHV-Baumraum ermöglicht.
Die Arbeit zeigt, dass der Durchmesser des Dualgraphen einer Anordnung von topologischen Scheiben durch eine Funktion von und der maximalen Anzahl der Zusammenhangskomponenten paarweiser Schnitte beschränkt ist, wobei für zwei Scheiben eine scharfe Schranke von und für den allgemeinen Fall eine Schranke von bewiesen wird.
Diese Arbeit untersucht die feingranulare Komplexität der Berechnung der -Hausdorff-Distanz unter Translationen und zeigt, wie sich Laufzeitgrenzen je nach Dimension, Diskretisierung und der Unterscheidung zwischen gerichteten und ungerichteten Varianten sowie asymmetrischen Größenverhältnissen der Punktmengen unterscheiden.
Diese Arbeit schließt die Lücke zwischen den bisherigen Schranken für den Spannungsverhältnis des gerichteten -Graphen, indem sie erstmals einen exakten und engen Wert von 5 beweist.
Die Arbeit zeigt, dass die Minimierung der längsten Kante bei der simultanen geometrischen Einbettung zweier Pfade auf einem ganzzahligen Gitter NP-schwer ist, während die Minimierung des Umfangs des umschließenden Gitters für den Fall, dass ein Pfad x-monoton und der andere y-monoton ist, in Zeit gelöst werden kann.
Diese Arbeit charakterisiert, wann die Band-Entfaltung eines verschachtelten Prismatoids eine nicht-überlappende Entfaltung ergibt, und zeigt dabei, dass das bekannte Gegenbeispiel im Wesentlichen der einzige mögliche Ausnahmefall ist.
Die Autoren stellen einen Gap-ETH-optimalen randomisierten Approximationsalgorithmus für das Traveling-Salesman-Problem und den Steiner-Baum in hyperbolischen Räumen vor, der auf einer neuartigen hybriden hyperbolischen Quadtree-Zerlegung und einer nicht-uniformen Portalplatzierung basiert.
Diese Arbeit verbessert den Laufzeitkomplexitätsfaktor für -Approximationsalgorithmen des -Median- und -Means-Clustering in niedrigdimensionalen euklidischen Räumen auf $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)$ und beweist unter der Gap-Exponential-Time-Hypothese, dass diese Laufzeit bis auf polylogarithmische Faktoren optimal ist.
Dieser Artikel untersucht Invarianten fast-einbettender Graphen in der Ebene, stellt Zusammenhänge zur Homologie des gelöschten Produkts her, konstruiert konkrete Beispiele und stellt die zugrundeliegenden algebraischen und geometrisch-topologischen Konzepte in einer für Nicht-Topologen verständlichen Sprache vor.
Dieses Paper stellt einen parametrenfreien Ansatz zur topologischen Vergröberung räumlicher Graphen vor, der durch eine neuartige, dreiecksbewusste Filtration und das Zusammenfalten kurzer Kanten die Graphengröße signifikant reduziert, während wesentliche topologische Merkmale unter Berücksichtigung räumlicher Informationen erhalten bleiben.
Diese Arbeit stellt eine hocheffiziente Methode zur Nachbarschaftssuche in 3D-Punktwolken vor, die durch die Kombination von Raumfüllenden Kurven mit linearen Oktbäumen und spezialisierten Suchalgorithmen die Laufzeit im Vergleich zu bestehenden Lösungen um bis zu das Zehnfache reduziert und eine hohe Parallelisierbarkeit aufweist.
Dieser Artikel entwickelt eine geometrische Beschreibung und einen Entwurfsprozess für Popup-Strukturen, die durch die Kombination von Origami und Kirigami entstehen, um maßgeschneiderte Formen mit variierender Krümmung für Anwendungen wie Strömungswiderstandsreduktion, Verpackung und Architektur zu ermöglichen.
Diese Arbeit untersucht die Nicht-Injektivität des VPHT bei Graphen mit kollinearen Eckpunkten und identifiziert notwendige sowie hinreichende Bedingungen für deren Nicht-Rekonstruierbarkeit.
Diese Arbeit liefert die erste formale Spezifikation und Analyse der Li-Chao-Baum-Datenstruktur, einschließlich vollständiger algorithmischer Beschreibungen, Korrektheitsbeweise, Komplexitätsanalysen und empirischer Leistungscharakterisierungen.
Der Artikel untersucht ein geometrisches Balancierspiel mit Linienanordnungen und zeigt, dass die minimale Anzahl von Steinen, die Alice benötigt, um einen Sieg von Bob zu verhindern, für jede Anordnung von Linien in allgemeiner Position beträgt und in polynomieller Zeit berechnet werden kann.
Diese Arbeit charakterisiert die Lösbarkeit von Permutations-Match-Puzzles auf -Gittern durch eine acyclische Bedingung, liefert eine Hook-Längen-Formel für die Anzahl der Lösungen und zeigt, dass das Finden minimaler Reparaturen bei einer Verallgemeinerung auf beliebige Permutationen NP-vollständig ist.
Dieser Artikel stellt eine topologisch stabile Variante der Hough-Transformation vor, die anstelle diskreter Abstimmungen eine kontinuierliche Bewertungsfunktion nutzt, um mittels persistenter Homologie effizient Kandidaten für Linien in Punktwolken zu identifizieren.
Der Artikel untersucht die Komplexität der Erweiterung von Storyline-Layouts durch das Einfügen fehlender Charaktere unter Minimierung der lokalen Kreuzungszahl und zeigt, dass das Problem bezüglich der Anzahl der eingefügten Charaktere und der maximalen Anzahl aktiver Charaktere W[1]-schwer, bezüglich der aktiven Charaktere in XP und bezüglich der Summe aus aktiven Charakteren und lokaler Kreuzungszahl in FPT liegt.
Die Arbeit stellt randomisierte Algorithmen vor, die für Einheits-Scheibengraphen und Scheibengraphen mit verschiedenen Radien in nahezu linearer bzw. parametrisierter Zeit -Approximationen für das Maximum-Clique-Problem berechnen und damit die bisherigen exakten Laufzeiten verbessern.