Online algorithms for searching and exploration in the plane

DOI10.1016/j.cosrev.2010.05.001zbMath1298.68280OpenAlexW2033124907MaRDI QIDQ465662

Subir Kumar Ghosh, Rolf Klein

Publication date: 24 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2010.05.001

zbMATH Keywords

shortest pathonline algorithmscompetitive ratiorandomized algorithmmotion planningcomputational geometryapproximation algorithmsexplorationminimum link pathtarget searchingvisibility polygonswatchman route

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Artificial intelligence for robotics (68T40) Online algorithms; streaming algorithms (68W27)

Related Items

Treasure Hunt with Advice ⋮ Evacuating an Equilateral Triangle in the Face-to-Face Model ⋮ Online graph exploration: New results on old and new algorithms ⋮ Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs ⋮ Impact of knowledge on the cost of treasure hunt in trees ⋮ On-line exploration of rectangular cellular environments with a rectangular hole ⋮ Deterministic treasure hunt in the plane with angular hints ⋮ Evacuating equilateral triangles and squares in the face-to-face model ⋮ Linear search by a pair of distinct-speed robots ⋮ The simple grid polygon exploration problem ⋮ Competitive Searching for a Line on a Line Arrangement. ⋮ Exploration of High-Dimensional Grids by Finite Automata

Cites Work

• Tight analysis of a self-approaching strategy for the online kernel-search problem
• Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
• Searching in the plane
• On-line path planning in an unknown polygonal environment
• Shortest watchman routes in simple polygons
• Shortest paths without a map
• Polygon exploration with time-discrete vision
• Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape
• Optimum watchman routes
• Search games
• Walking an unknown street with bounded detour
• Star search -- a different show
• How to find a point on a line within a fixed distance
• Optimal on-line algorithms for walking with minimum number of turns in unknown streets
• The theory of search games and rendezvous.
• Searching and on-line recognition of star-shaped polygons.
• Competitive searching in a generalized street
• On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
• Competitive exploration of rectilinear polygons
• Online searching with turn cost
• On the linear search problem
• Yet more on the linear search problem
• The Polygon Exploration Problem
• Self-adjusting binary search trees
• How to learn an unknown environment. I
• Minimax Solutions for Linear Search Problems
• Optimal Constructions of Hybrid Algorithms
• AN ON-LINE ALGORITHM FOR NAVIGATING IN AN UNKNOWN ENVIRONMENT
• Online Navigation in a Room
• Navigating in Unfamiliar Geometric Terrain
• An Online Algorithm for Improving Performance in Navigation
• Generalized streets revisited
• An Optimal Competitive Strategy for Walking in Streets
• LOWER BOUNDS FOR STREETS AND GENERALIZED STREETS
• Dynamic path planning for a mobile automaton with limited information on the environment
• Walking streets faster
• Going home through an unknown street
• Visibility Algorithms in the Plane
• Algorithmische Geometrie
• The ultimate strategy to search on \(m\) rays?
• Parallel searching on \(m\) rays
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item