37 papers
Dit artikel presenteert een nieuwe methode om gebieden met een tekort aan koelcentra te identificeren door persistent homologie toe te passen op een gefilterd getuige-complex, waarbij de resultaten worden vergeleken met traditionele hittekwetsbaarheidsindices om een vollediger beeld van de risico's te krijgen.
Deze paper introduceert een nieuwe definitie van subgradienten voor Hadamard-ruimten, gebaseerd op Busemann-functies, waarmee stochastische en incrementele subgradiëntmethoden met gegarandeerde complexiteitsgrenzen kunnen worden toegepast op convex optimalisatieproblemen zoals het berekenen van medians in BHV-boomruimten.
Dit artikel bewijst dat de diameter van het duale graaf van een rangschikking van topologische schijven in het vlak begrensd kan worden door een functie van en het maximale aantal samenhangende componenten van de doorsneden van twee schijven, met specifieke schattingen voor zowel twee als schijven.
Dit artikel onderzoekt de fijnmazige complexiteit van het berekenen van de -Hausdorff-afstand onder translaties en onthult een ingewikkeld samenspel tussen dimensionaliteit, symmetrie en discretisatie, waarbij de auteurs nieuwe bijna-lineaire algoritmen, conditionele ondergrenzen en complexiteitsbarrières voor verschillende varianten (gericht/ongericht, continu/discreet) in diverse dimensies aantonen.
Deze paper sluit de bestaande kloof tussen de onder- en bovengrens voor de spanverhouding van de gerichte -graf door te bewijzen dat deze verhouding exact 5 is, wat de eerste strakke ondergrens is voor een -graf.
Dit artikel toont aan dat het minimaliseren van de lengte van de langste rand bij de simultane geometrische embedding van twee paden op een rooster NP-moeilijk is, en biedt een -algoritme om de omtrek van het rooster te minimaliseren wanneer één pad x-monotoon en het andere y-monotoon is.
Dit artikel karakteriseert wanneer de band-ontvouwing van geneste prismatoiden niet-overlappend is, en toont aan dat het bekende tegenvoorbeeld in zekere zin het enige mogelijke tegenvoorbeeld is, waardoor de inzichten worden verdiept voor het oplossen van het bredere Dürer-probleem.
Deze paper presenteert Gap-ETH-tighte randomiseerde algoritmen voor het TSP en het Steiner-boomprobleem in hyperbolische ruimte, die een -benadering bieden in tijd $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$ door middel van een nieuwe 'hybrid hyperbolic quadtree'-decompositie en een niet-uniforme portal-plaatsing.
Dit paper verbetert de looptijd voor -benaderingsalgoritmen voor -median en -means clustering in laagdimensionale Euclidische ruimtes en bewijst een bij benadering overeenkomende ondergrens onder de Gap Exponentiële Tijd Hypothese.
Dit artikel onderzoekt invarianten van bijna-embeddings van grafen in het vlak, legt verbanden met de homologie van het verwijderde product van een graaf, construeert voorbeelden die bepaalde invariantewaarden realiseren, en presenteert deze concepten in een toegankelijke taal voor niet-topologen terwijl het open problemen en conjecturen aan de voorhoede van het onderzoek belicht.
Deze paper introduceert een parameterloze methode voor het coarsenen van ruimtelijke grafen door korte randen in te storten, waarbij een nieuwe 'triangle-aware' filtratie wordt gebruikt om de topologische kenmerken te behouden en de methode invariant is onder rotatie, translatie en schaling.
Dit paper introduceert een efficiënte methode voor het zoeken naar buren in 3D-puntenwolken door ruimtevullende krommen en lineaire octrees te combineren, wat leidt tot een tot 10 keer snellere zoektijd en een aanzienlijke reductie in cache-misses vergeleken met bestaande oplossingen.
Dit artikel introduceert een geometrisch ontwerpproces voor pop-upstructuren die, door een combinatie van vouwen en snijden, kunnen worden omgezet in voorgeprogrammeerde vormen met variërende krommingen voor toepassingen zoals dragreductie en architectuur.
Dit artikel onderzoekt onder welke voorwaarden de verbale persistente homologie-transformatie (VPHT) niet-injectief is voor graafstructuren met collineaire hoekpunten, en identificeert zowel noodzakelijke als voldoende eigenschappen voor het niet-reconstrueerbaar zijn van dergelijke grafen.
Dit artikel biedt de eerste formele specificatie van de Li-Chao-boom, inclusief volledige algoritmische beschrijvingen, correctheidswijzen, theoretische complexiteitsanalyse en empirische prestatiekenmerken, waarmee het een definitieve referentie wordt voor deze datastructuur die tot nu toe vooral bekend was uit de competitieve programmering.
Dit artikel bepaalt het minimale aantal stenen dat Alice nodig heeft om Bob te weerhouden van het leegmaken van een vakje in een geometrisch spel met lijnarrangementen, en toont aan dat dit aantal voor lijnen in algemene positie evenredig is met .
Dit artikel introduceert permutatie-matchpuzzels op roosters, karakteriseert de oplosbaarheid ervan via een acyclische voorwaarde, levert een tellende formule voor oplossingen, biedt een lineaire algoritme voor het repareren van onoplosbare gevallen, en toont aan dat de veralgemening met willekeurige permutaties NP-compleet is.
Deze paper introduceert een topologisch stabiele variant van de Hough-transformatie die, in plaats van een gediscrétiseerde stemming, een continue scorefunctie en persistente homologie gebruikt om lijnen in puntwolken te detecteren, vergezeld van een efficiënt algoritme voor de berekening van deze kandidaatlijnen.
Dit artikel onderzoekt het probleem van het uitbreiden van vaste storyline-layouts met nieuwe karakters terwijl de vergaderingsrestricties worden gehandhaafd, en bewijst dat het minimaliseren van het lokale kruisingsgetal W[1]-hard is geparametriseerd door het aantal toegevoegde karakters plus het maximale aantal actieve karakters, maar wel in XP ligt voor het laatste en in FPT voor de som van het maximale aantal actieve karakters en het lokale kruisingsgetal.
Deze paper presenteert geoptimaliseerde, gerandomiseerde algoritmen die voor unit disk graphs en disk graphs met verschillende stralen een -benadering van de maximale clique in bijna lineaire tijd berekenen.