論文の概要: Mend the gap: A smart repair algorithm for noisy polygonal tilings
- arxiv url: http://arxiv.org/abs/2312.11415v1
- Date: Mon, 18 Dec 2023 18:18:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-20 19:09:57.884612
- Title: Mend the gap: A smart repair algorithm for noisy polygonal tilings
- Title（参考訳）: mend the gap: ノイズ多角形タイルのスマート修復アルゴリズム
- Authors: Jeanne N. Clelland
- Abstract要約: 一般に、$T$ は、ギャップの存在と、$T*$ のポリゴン間の重なり合いのため、近似的タイリングにしかならない。
tt smart_repairと呼ばれる新しいアルゴリズムを導入し、$T$のポリゴンを修正して、$T*$に近いタイリングを生成する。
このアルゴリズムのモチベーションは、より小さな地理的単位から地区を構築するためにアルゴリズムが使用される計算再分断から来ている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let $T^* = \{P^*_1, \ldots, P^*_N\}$ be a polygonal tiling of a simply
connected region in the plane, and let $T = \{P_1, \ldots, P_N\}$ be a noisy
version of $T^*$ obtained by making small perturbations to the coordinates of
the vertices of the polygons in $T^*$. In general, $T$ will only be an
approximate tiling, due to the presence of gaps and overlaps between the
perturbed polygons in $T$. The areas of these gaps and overlaps are typically
small relative to the areas of the polygons themselves.
Suppose that we are given the approximate tiling $T$ and we wish to recover
the tiling $T^*$. To address this problem, we introduce a new algorithm, called
{\tt smart\_repair}, to modify the polygons in $T$ to produce a tiling
$\widetilde{T} = \{\widetilde{P}_1, \ldots, \widetilde{P}_N\}$ that closely
approximates $T^*$, with special attention given to reproducing the {\em
adjacency relations} between the polygons in $T^*$ as closely as possible.
The motivation for this algorithm comes from computational redistricting,
where algorithms are used to build districts from smaller geographic units.
Because districts in most U.S. states are required to be contiguous, these
algorithms are fundamentally based on adjacency relations between units.
Unfortunately, the best available map data for unit boundaries is often noisy,
containing gaps and overlaps between units that can lead to substantial
inaccuracies in the adjacency relations. Simple repair algorithms can
exacerbate these inaccuracies, with the result that algorithmically drawn
districts based on the ``repaired" units may be discontiguous, and hence not
legally compliant. The algorithm presented here is specifically designed to
avoid such problems.
A Python implementation is publicly available as part of the MGGG
Redistricting Lab's {\tt Maup} package, available at
\url{https://github.com/mggg/maup}.
- Abstract（参考訳）: t^* = \{p^*_1, \ldots, p^*_n\}$ を平面内の単連結領域の多角形ティリングとし、$t = \{p_1, \ldots, p_n\}$ を$t^*$ で多角形の頂点の座標に小さな摂動によって得られる$t^*$ のノイズバージョンとする。
一般に、$t$は、摂動多角形の間のギャップと重なりが$t$で存在するため、近似的なタイリングである。
これらのギャップと重なり合いの領域は、典型的にはポリゴン自体の領域と比較して小さい。
およそのティリング$t$ が与えられ、ティリング$t^*$ を回収したいと仮定する。
この問題に対処するために、新しいアルゴリズムである {\tt smart\_repair} を導入して、$t$ で多角形を修飾し、$t^*$ で多角形間の共役関係を再現するために、$t^*$ と密接に近似する$\widetilde{t} = \{\widetilde{p}_1, \ldots, \widetilde{p}_n\}$ を生成する。
このアルゴリズムの動機は、より小さな地理的単位からディストリクトを構築するためにアルゴリズムを使用する計算再帰にある。
合衆国のほとんどの州の地区は連続性が必要であるので、これらのアルゴリズムは基本的に単位間の隣接関係に基づいている。
残念ながら、単位の境界に関する最良の地図データは、しばしば騒がしく、隣接関係のかなりの不正確さにつながる単位間のギャップと重なりを含んでいる。
単純な修復アルゴリズムは、これらの不正確さを悪化させ、`repaired'ユニットに基づいてアルゴリズム的に地区を描画する結果が不連続であり、従って法的に適合しない可能性がある。
ここで示されるアルゴリズムは、このような問題を避けるために特別に設計されている。
Pythonの実装は、MGGG Redistricting Lab's {\tt Maup}パッケージの一部として公開されており、 \url{https://github.com/mggg/maup}で利用可能である。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。
スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文 参考訳（メタデータ） (2023-02-20T18:45:24Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Improved No-Regret Algorithms for Stochastic Shortest Path with Linear
MDP [31.62899359543925]
線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。
我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。
第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
論文 参考訳（メタデータ） (2021-12-18T06:47:31Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Covering Polygons is Even Harder [0.0]
MCCはMINIMUM CONVEX COVER問題において$mathsfNP$-hardであることが知られている。
MCC が $existmathbbR$-hard であることを証明する。
論文 参考訳（メタデータ） (2021-06-04T08:29:48Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。