Online Vertex Exploration Problems in a Simple Polygon

スポンサーリンク

概要

• 論文の詳細を見る

• This paper considers online vertex exploration problems in a simple polygon where starting from a point in the inside of a simple polygon, a searcher is required to explore a simple polygon to visit all its vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.

著者

• Katoh Naoki

  Department Of Architecture And Architectural Engineering Kyoto University

• Katoh Naoki

  Department of Architecture and Architectural Engineering, Kyoto University

• HIGASHIKAWA Yuya

  Department of Architecture and Architectural Engineering, Kyoto University

関連論文

• DS-1-7 無交差ラーマンフレームワーク列挙アルゴリズム(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
• The Bacteriology of Acne Vulgaris and Antimicrobial Susceptibility of Propionibacterium acnes and Staphylococcus epidermidis Isolated from Acne Lesions
• 1B2 The Multicover Problem in Graphs arising from Patrol Route Planning
• An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity(Invited Papers from New Horizons in Computing)
• AN EFFICIENT ALGORITHM FOR BICRITERIA MINIMUM-COST CIRCULATION PROBLEM
• Finding a Triangular Mesh with a Constant Number of Different Edge Lengths(Invited Papers from New Horizons in Computing)
• AN ε-APPROXIMATION SCHEME FOR MINIMUM VARIANCE PROBLEMS
• Online Vertex Exploration Problems in a Simple Polygon

スポンサーリンク