Evaluating Cooling Center Coverage Using Persistent Homology of a Filtered Witness Complex
이 논문은 지속적 호몰로지를 기반으로 한 필터링된 위시너스 복합체를 활용하여 냉방 센터의 공백을 분석하고, 이를 기존 열 취약성 지수 (HVI) 와 비교함으로써 극심한 폭염으로 인한 사망 위험 지역을 다각적으로 파악하는 새로운 접근법을 제시합니다.
💻 Category
cs.CG
37 편의 논문
Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces
이 논문은 Hadamard 공간에서 선형 구조의 부재로 인한 어려움을 극복하기 위해 Busemann 함수에 기반한 새로운 하위 기울기 (subgradient) 개념을 도입하고, 이를 통해 확률적 및 점진적 하위 기울기 방법의 일반화와 복잡성 보장을 가능하게 하여 BHV 트리 공간의 중앙값 계산 등 다양한 최적화 문제에 적용할 수 있음을 제시합니다.
On the Diameter of Arrangements of Topological Disks
이 논문은 평면상의 개의 위상적 원판으로 구성된 배열의 이면도 (dual graph) 지름이 원판 쌍별 교차 성분 수의 최댓값 와 의 함수로 유계임을 증명하고, 특히 두 원판의 경우 지름이 $2\DeltanO(n^3 2^n \Delta)$로 상한을 제시합니다.
Computing Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
이 논문은 노름 하에서 점 집합 간의 최소 하우스도르프 거리를 계산하는 문제에서 차원, 방향성 (지향성/비지향성), 그리고 연속성/이산성 간의 복잡한 상호작용을 정밀한 복잡도 분석을 통해 규명하고, 각 변형에 대한 새로운 상한 및 하한을 제시합니다.
The Spanning Ratio of the Directed -Graph is 5
이 논문은 방향성 -그래프의 스패닝 비율이 기존에 알려진 4 에서 7 사이의 범위에서 5 로 정확히 결정됨을 증명하여, 모든 -그래프 중 최초로tight bound 를 제시했습니다.
Simultaneous Embedding of Two Paths on the Grid
이 논문은 두 개의 경로를 격자 위에 동시에 매립할 때 가장 긴 변의 길이를 최소화하는 문제가 NP-난해임을 증명하고, 한 경로가 x-단조적이고 다른 경로가 y-단조적인 경우 격자의 둘레를 시간에 최소화할 수 있음을 보여줍니다.
Prismatoid Band-Unfolding Revisited
이 논문은 중첩된 프리즘토이드의 밴드-언폴딩이 겹치지 않는 전개도를 생성하는지 판별하는 기준을 제시하고, 기존 반례가 사실상 유일한 반례임을 증명하여 더 나아가 비중첩 경우 해결에 기여할 수 있는 도구를 개발했습니다.
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
이 논문은 Gap-ETH 하에서 최적의 의존성을 갖는 차원 쌍곡 공간의 TSP 및 스테이너 트리 문제에 대한 -근사 알고리즘을 제시하며, 이를 위해 '하이브리드 쌍곡 쿼드트리'와 같은 새로운 기하학적 구조와 분석 기법을 도입했습니다.
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
이 논문은 저차원 유클리드 공간에서 -median 및 -means 클러스터링 문제에 대해 기존 결과를 개선한 거의 최적의 상한 알고리즘을 제시하고, 갭 지수 시간 가설 하에서 거의 일치하는 하한을 증명합니다.
Invariants of almost embeddings of graphs in the plane
이 논문은 평면 내 거의 매장 (almost embeddings) 그래프의 불변량들 간의 관계를 증명하고, 이를 그래프의 삭제된 곱 (deleted product) 의 호몰로지와 연결하며, 대수적 및 기하학적 위상수학의 핵심 아이디어를 비전문가도 이해할 수 있는 언어로 제시하고 있습니다.
Topological Spatial Graph Coarsening
이 논문은 공간 그래프의 노드 수를 줄이면서도 주요 위상적 특성을 보존하기 위해 삼각형 인식 여과 (triangle-aware graph filtration) 와 지속적 다이어그램을 활용한 매개변수 없는 위상적 공간 그래프 축소 기법을 제안하고, 회전·이동·확대에 대한 불변성을 증명하여 그 유효성을 입증합니다.
Efficient Neighbourhood Search in 3D Point Clouds Through Space-Filling Curves and Linear Octrees
이 논문은 공간 채움 곡선 (Morton 및 Hilbert) 과 선형 옥트리를 결합하여 3D 포인트 클라우드의 이웃 검색 시 캐시 미스를 25~75% 줄이고 기존 솔루션 대비 최대 10 배 빠른 성능을 달성하는 효율적인 방법론을 제안합니다.
Geometry and design of popup structures
이 논문은 오리가미와 키리가미의 기하학적 원리를 응용하여 팝업 구조의 곡률을 정의하고, 이를 통해 원하는 형상의 팝업 구조물을 설계할 수 있는 방법론을 제시함과 동시에 단일 패턴으로 곡률 변화를 구현하는 가능성을 실험을 통해 검증했습니다.
Which Vertical Graphs are Non VPHT Reconstructible?
이 논문은 VPHT(Verbose Persistent Homology Transform) 가 일반적으로 주형 복원이 가능하다는 전제 하에, 모든 꼭짓점이 한 직선 위에 있는 그래프와 같은 특이한 경우를 분석하여 VPHT 가 주형 복원이 불가능한 그래프의 필요 및 충분 조건을 규명합니다.
The Li-Chao Tree: Algorithm Specification and Analysis
이 논문은 경쟁 프로그래밍 커뮤니티에서 널리 사용되지만 공식적인 학술 규격이 부재했던 '리차오 트리'에 대한 최초의 공식 명세서를 제시하며, 완전한 알고리즘 사양, 형식적 정확성 증명, 이론적 복잡도 분석 및 실증적 성능 평가를 포함합니다.
Geometric Give and Take
이 논문은 1977 년 스펜서가 제안한 균형 게임의 기하학적 변형인 직선 배열에 대한 게임을 분석하여, 앨리스가 밥이 승리하는 것을 막기 위해 필요한 최소 돌 개수가 다항 시간 내에 계산 가능하며 임의의 일반 위치 직선 배열에 대해 차수임을 증명했습니다.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
이 논문은 행과 열의 순서 제약 조건을 가진 격자 퍼즐의 해 존재 조건을 분석하고, 해의 개수를 훅 길이 공식으로 계산하며, 해가 없는 경우의 최소 수정 알고리즘을 제시하고 일반화된 버전의 NP-완전성을 증명합니다.
Topologically Stable Hough Transform
이 논문은 이산적 투표 방식을 연속적인 점수 함수로 대체하고 지속적 호몰로지의 지속적 특징을 활용하여 점군에서 선을 탐지하는 새로운 형태의 호프 변환을 제안하고, 이를 효율적으로 계산하는 알고리즘을 구현했습니다.
The Complexity of Extending Storylines with Minimum Local Crossing Number
이 논문은 고정된 하위 스토리라인에 누락된 캐릭터를 추가하여 모든 미팅 제약을 유지하면서 단일 캐릭터별 최대 교차 수 (국소 교차 수) 를 최소화하는 문제의 매개변수화 복잡도 (W[1]-난해성, XP, FPT) 를 규명합니다.
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
이 논문은 단위 원판 그래프와 개의 서로 다른 반지름을 가진 일반 원판 그래프에 대해, 각각 및 시간 복잡도를 갖는 확률적 근사 알고리즘을 제안하여 최대 클릭 문제를 해결하는 새로운 접근법을 제시합니다.