抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
最小Convex Cover(MCC)問題において,著者らは単純な多角形Pと整数kを与えて,この質問は結合がPであるk凸多角形が存在するかどうかである。MCCはNP困難である[Culbson&Reckwow:Covering polygonsは硬く,FOCS 1988/Journal of Algorith 1994]で,また∃R[O’Rourkeでは,多角形,Allerton 1982]に対する最小凸カバーの計算の複雑さが知られている。MCCは∃R-ハードであり,従って,問題は∃R-完全であることを証明した。言い換えれば,この問題は多項式方程式と整数係数の不等式が実解を持つかどうかを決定するのに等価である。著者らが構築した多角形のカバーが存在するならば,次に,三角形から成るカバーがある。したがって,副産物として,k三角形が与えられた多角形をカバーするかどうかを決定するのに,それは∃R完全であることも確立した。最小カバーを見つけるのが,N Pにあるかどうかは,文献において繰り返し上げられており,2001年[Eidenbenz&Widmayer:対数性能保証による最小凸カバーのための近似アルゴリズム,計算2003年におけるESA 2001/SIAM Journal]の「長年のオープン質問」として言及された。NP= ∃R,この問題はN Pではなく,この結果の意味は,小さなカバーを見つけるための多くの自然なアプローチが,最適解における片の隅角に対して,任意に高い代数的度合の不合理な座標を必要とするので,いくつかの場合で準最適解を与えるのに結びついていることを,著者らは証明する。”その問題”は,いくつかの事例において,多くの自然アプローチが,いくつかの場合において,多くの自然アプローチが結合されるということを,証明するものであると,証明する。”その結論”は,いくつかの事例において,小さなカバーを見つけるための多くの自然なアプローチが,最適解法における部分の隅角のために必要とされる,という事を証明した。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
