The Polygon Exploration Problem

DOI10.1137/S0097539799348670zbMath0994.68163MaRDI QIDQ2784471

Klaus Kriegel, Christian Icking, Frank Hoffmann, Rolf Klein

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

navigationpolygonon-line algorithmmotion planningcomputational geometryrobotcurve lengthcompetitive strategyangle hulloptimum watchman tour

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40)

Related Items (33)

Competitive exploration of rectilinear polygons ⋮ Inspecting a Set of Strips Optimally ⋮ An Improved On-line Strategy for Exploring Unknown Polygons ⋮ Online exploration outside a convex obstacle ⋮ An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem ⋮ Worst-case optimal exploration of terrains with obstacles ⋮ Improved exploration of unknown polygons ⋮ Optimality and competitiveness of exploring polygons by mobile robots ⋮ Evacuating two robots from multiple unknown exits in a circle ⋮ Search on a Line by Byzantine Robots ⋮ Reconstructing visibility graphs with simple robots ⋮ Priority evacuation from a disk: the case of \(n \geq 4\) ⋮ Online algorithms for searching and exploration in the plane ⋮ Characterizing and recognizing LR-visibility polygons ⋮ Better Upper Bounds for Searching on a Line with Byzantine Robots ⋮ Communication and location discovery in geometric ring networks ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ COMPETITIVE COMPLEXITY OF MOBILE ROBOT ON-LINE MOTION PLANNING PROBLEMS ⋮ LEAVING AN UNKNOWN MAZE USING AN ERROR-PRONE COMPASS ⋮ Search on a line with faulty robots ⋮ Online searching with an autonomous robot ⋮ The simple grid polygon exploration problem ⋮ Online searching with turn cost ⋮ Weighted nearest neighbor algorithms for the graph exploration problem on cycles ⋮ Competitive searching over terrains ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Exploring and Triangulating a Region by a Swarm of Robots ⋮ COVERING A POINT SET BY TWO DISJOINT RECTANGLES ⋮ Competitive Searching for a Line on a Line Arrangement. ⋮ Energy Consumption of Group Search on a Line ⋮ Reconstructing Visibility Graphs with Simple Robots ⋮ Polygon exploration with time-discrete vision ⋮ Group search of the plane with faulty robots

This page was built for publication: The Polygon Exploration Problem