Evaluating Cooling Center Coverage Using Persistent Homology of a Filtered Witness Complex
この論文は、極端な暑さのリスクを評価するために、永続ホモロジーを用いた冷却センターの被覆ギャップの分析と、従来の熱脆弱性指数（HVI）を組み合わせることで、より包括的な脆弱性評価を実現する手法を提案し、4 つの都市で検証したことを示しています。
💻 Category
cs.CG
37 件の論文
Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces
この論文は、非線形構造を持つハダマード空間における凸最適化の課題を解決するため、ブセマン関数に基づく新たな部分勾配の概念を提案し、これにより確率的および増分部分勾配法の一般化と複雑性保証、ならびに BHV 樹空間におけるメディアン計算などの応用を可能にしています。
On the Diameter of Arrangements of Topological Disks
この論文は、平面内の個の位相的円盤からなる配置の双対グラフの直径が、円盤の交差成分数の最大値との関数として有界であることを示し、特にの場合に直径が以下であることを証明するとともに、一般のに対してという上界を導出したものである。
Computing Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
本論文は、点集合間のハウスドルフ距離の最小化問題において、次元数、対称性（有向・無向）、および連続・離散の区別が計算複雑性に及ぼす影響を、微細な複雑性理論を用いて体系的に分析し、特に次元や入力サイズ比に応じた非対称な時間計算量や、3SUM 仮説との関係など、新たな理論的限界とアルゴリズムを明らかにしたものである。
The Spanning Ratio of the Directed -Graph is 5
この論文は、幾何グラフの一種である有向グラフのスパニング比が、以前は4から7の間と推定されていたのに対し、線形計画法を用いた新規な証明により、その tight な値が厳密に5であることを示すものである。
Simultaneous Embedding of Two Paths on the Grid
この論文は、2 つのパスの同時幾何学的埋め込みにおける最長辺の長さの最小化が NP 困難であることを示し、一方のパスが x 単調でもう一方が y 単調である場合、その埋め込みを含む整数グリッドの周長を 時間で最小化できることを証明しています。
Prismatoid Band-Unfolding Revisited
本論文は、ネスト型プリズムトイドのバンド展開が重なりを生じないための条件を特徴づけ、既知の反例が本質的に唯一の反例であることを示すことで、ダル問題の未解決部分に対する理解を深める新たな手法を提供する。
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
この論文は、Gap-ETH 下で最適であることが示された $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}d(1+\varepsilon)$-近似解法として提示するものである。
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
この論文は、低次元ユークリッド空間における-median および-means 問題の-近似アルゴリズムの実行時間を大幅に改善し、さらに Gap Exponential Time 仮説の下でその実行時間の下限がほぼ一致することを示しています。
Invariants of almost embeddings of graphs in the plane
この論文は、平面におけるグラフの「ほぼ埋め込み」の不変量とその関係性を証明し、削除された積のホモロジーとの関連を示すとともに、代数位相幾何学の概念を非専門家にも理解しやすい形で提示し、未解決問題や予想を提示するものである。
Topological Spatial Graph Coarsening
本論文は、空間グラフのトポロジカル特徴を保持しつつノード数を削減するパラメータ不要の手法を提案し、三角形を考慮した新しいフィルトレーションに基づく永続的図の適応と、回転・並進・スケーリングに対する等変性を保証する理論的性質を特徴とする。
Efficient Neighbourhood Search in 3D Point Clouds Through Space-Filling Curves and Linear Octrees
この論文は、空間充填曲線（モートン曲線やヒルベルト曲線）による空間再順序付けと線形オクトリーを組み合わせることで、3 次元点雲の近傍探索におけるキャッシュミスや実行時間を大幅に削減し、既存手法と比較して最大 10 倍の高速化と 40 コア環境での 36 倍のスケーラビリティを実現する効率的な手法を提案しています。
Geometry and design of popup structures
この論文は、折り紙と切り紙の技法を組み合わせたポップアップ構造の幾何学的設計手法を確立し、単一の切断・折りパターンから負から正の曲率へ変化する多様な形状を実現する設計パイプラインを提案し、その実証実験とドラッグ低減・包装・建築ファサードへの応用可能性を示しています。
Which Vertical Graphs are Non VPHT Reconstructible?
本論文は、頂点がすべて同一直線上に並ぶグラフ（垂直グラフ）に焦点を当て、一般位置の仮定が成り立たない場合における垂直持続的ホモロジー変換（VPHT）の非単射性、すなわち形状の再構成不可能性に関する必要十分条件を特定し、その完全な分類に向けた知見を提供するものである。
The Li-Chao Tree: Algorithm Specification and Analysis
この論文は、競技プログラミングで広く用いられているが正式な仕様書が存在しなかった「Li-Chao 木」の完全なアルゴリズム仕様、形式的な正しさの証明、理論的複雑性の分析、および実証的な性能評価を提供し、その実装の簡便性や数値的安定性、永続性などの高度な変種への拡張性を含む最終的な仕様書として確立するものである。
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
この論文は、単位円盤グラフおよび半径が種類である円盤グラフにおいて、確率的な手法を用いて最大クリークを近似的に解くアルゴリズムを提案し、それぞれほぼ線形時間およびパラメータ化近似スキームを実現したものである。