37 articoli
Questo studio utilizza l'omologia persistente applicata a un complesso testimone filtrato per identificare le lacune nella copertura dei centri di raffrescamento in diverse città statunitensi, confrontando i risultati con un indice di vulnerabilità al calore per fornire una valutazione più completa delle aree a rischio di mortalità legata al caldo.
Questo articolo introduce un nuovo tipo di subgradiente basato sulle funzioni di Busemann per spazi di Hadamard, permettendo di generalizzare i metodi stocastici e incrementali di subgradiente con garanzie di complessità e applicandoli a problemi come il calcolo delle medie -e nelle varietà BHV degli alberi.
Il documento dimostra che il diametro del grafo duale di un'arrangiamento di dischi topologici nel piano è limitato da una funzione di e del numero massimo di componenti connesse nell'intersezione tra due dischi, fornendo stime specifiche come per il caso generale e per due dischi.
Questo lavoro analizza la complessità computazionale fine della distanza di Hausdorff tra insiemi di punti sotto traslazioni, rivelando come dimensione, simmetria (distanza diretta vs. indistinta) e discrezione (continuo vs. discreto) influenzino in modo intricato i limiti superiori e inferiori del tempo di esecuzione, fornendo nuovi algoritmi quasi-lineari e dimostrando la durezza condizionale per diverse varianti del problema.
Questo articolo risolve il problema del rapporto di allungamento del grafo diretto , dimostrando che il limite superiore stretto è esattamente 5, chiudendo così il divario tra i precedenti limiti inferiori e superiori e fornendo la prima prova di un limite stretto per qualsiasi grafo .
Il documento dimostra che minimizzare la lunghezza dell'arco più lungo nell'embedding geometrico simultaneo di due percorsi su una griglia intera è NP-difficile, mentre presenta un algoritmo di complessità per minimizzare il perimetro della griglia quando uno dei percorsi è monotono in e l'altro in .
Questo articolo caratterizza le condizioni in cui lo sviluppo a nastro di un prismatico annidato è privo di sovrapposizioni, dimostrando che il noto controesempio è sostanzialmente l'unico caso possibile e fornendo strumenti utili per affrontare il problema generale dell'apertura non sovrapposta dei prismatoidi.
Il paper presenta uno schema di approssimazione Gap-ETH-ottimale per il TSP e il problema dell'albero di Steiner nello spazio iperbolico -dimensionale, basato su una nuova decomposizione gerarchica chiamata "hybrid hyperbolic quadtree" e su un'analisi di attraversamento pesata.
Questo lavoro migliora i tempi di esecuzione degli algoritmi di approssimazione per i problemi di clustering -median e -means in spazi euclidei a bassa dimensione e dimostra che tale miglioramento è quasi ottimale, fornendo un limite inferiore corrispondente basato sull'ipotesi Gap Exponential Time.
Questo articolo introduce gli "quasi-embedding" di grafi nel piano, stabilisce relazioni tra i loro invarianti collegandoli all'omologia del prodotto cancellato, costruisce esempi specifici e presenta concetti di topologia algebrica e geometrica in modo accessibile agli studenti, pur affrontando problemi aperti della ricerca avanzata.
Questo lavoro propone un metodo di coarsening per grafi spaziali, privo di parametri e invariante rispetto a trasformazioni geometriche, che riduce la dimensione della rete preservandone le caratteristiche topologiche attraverso l'uso di un nuovo filtraggio "triangle-aware" e diagrammi di persistenza adattati.
Questo lavoro presenta un metodo efficiente per la ricerca di vicini in nuvole di punti 3D, combinando curve spazio-pienezza e un otto-albero lineare per ridurre i fallimenti della cache e accelerare le query fino a 10 volte rispetto alle soluzioni esistenti, con un'elevata scalabilità parallela.
Questo articolo esplora la geometria delle strutture pop-up, combinando origami e kirigami per sviluppare un modello geometrico e una pipeline di progettazione che permettono di creare strutture con curvature variabili e transizioni da superfici negative a positive, con applicazioni nel campo della riduzione della resistenza aerodinamica, del packaging e delle facciate architettoniche.
Questo lavoro indaga le condizioni di non iniettività della trasformata di omologia persistente verbosa (VPHT) su grafi i cui vertici sono tutti allineati, identificando proprietà necessarie e sufficienti per la loro non ricostruibilità.
Questo articolo fornisce la prima formalizzazione peer-reviewed dell'albero di Li-Chao, presentandone le specifiche algoritmiche complete, le dimostrazioni di correttezza formale, l'analisi della complessità teorica e la caratterizzazione delle prestazioni empiriche.
Il documento determina il numero minimo di sassolini necessario affinché Alice possa vincere un gioco di bilanciamento geometrico su un'arrangiamento di rette, dimostrando che tale valore è e calcolabile in tempo polinomiale.
Questo articolo caratterizza i "permutation match puzzles" su griglie, dimostrando che la loro risolubilità dipende dall'assenza di cicli nel grafo dei vincoli, fornendo una formula per il numero di soluzioni e un algoritmo lineare per le riparazioni minime nel caso semplice, mentre stabilisce che il problema diventa NP-completo quando si generalizzano i vincoli a permutazioni arbitrarie.
Il paper propone una nuova formulazione della trasformata di Hough basata sull'omologia persistente per rilevare linee in nuvole di punti, sostituendo lo schema di votazione discretizzato con una funzione di punteggio continua e fornendo un algoritmo efficiente per calcolare le linee candidate.
Questo articolo studia la complessità computazionale dell'estensione di layout di storie temporali con un numero di incroci locali minimo, dimostrando che il problema è W[1]-duro rispetto al numero di personaggi inseriti e a quello attivi, ma ammette soluzioni in XP e FPT sotto specifici parametri.
Questo articolo presenta algoritmi randomizzati che calcolano approssimazioni del massimo clique in grafi di dischi con tempi di esecuzione quasi lineari, offrendo una soluzione quasi lineare per i grafi di dischi unitari e uno schema di approssimazione parametrizzato per grafi con raggi distinti.