Searching in the plane
From MaRDI portal
Publication:690242
DOI10.1006/inco.1993.1054zbMath0781.68044OpenAlexW2019729116MaRDI QIDQ690242
Ricardo A. Baeza-Yates, Gregory J. E. Rawlins, Joseph C. Culberson
Publication date: 20 December 1993
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/1dd4bdbcf99e69e0e2cbe1f52d39c40a809447d9
Related Items
Linear Search with Terrain-Dependent Speeds ⋮ Position-independent near optimal searching and on-line recognition in star polygons ⋮ Best-of-both-worlds analysis of online search ⋮ Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ Impact of knowledge on the cost of treasure hunt in trees ⋮ Triangle evacuation of 2 agents in the wireless model (extended abstract) ⋮ Search on a Line by Byzantine Robots ⋮ Weighted online search ⋮ Overcoming probabilistic faults in disoriented linear search ⋮ Optimal circle search despite the presence of faulty robots ⋮ Delivery to safety with two cooperating robots ⋮ Algorithms for \(p\)-Faulty Search on a half-line ⋮ Online search with a hint ⋮ Deterministic treasure hunt and rendezvous in arbitrary connected graphs ⋮ Finding defectives on a line by random docking and interval group tests ⋮ Parametrized Metrical Task Systems ⋮ Lower bounds in on-line geometric searching ⋮ The ultimate strategy to search on \(m\) rays? ⋮ Parallel searching on \(m\) rays ⋮ Fast two-robot disk evacuation with wireless communication ⋮ On-line single-server dial-a-ride problems ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers ⋮ Time-energy tradeoffs for evacuation by two robots in the wireless model ⋮ Unnamed Item ⋮ On the approximation of shortest escape paths ⋮ Bike assisted evacuation on a line ⋮ On-line parallel heuristics, processor scheduling and robot searching under the competitive framework ⋮ Competitive online routing in geometric graphs ⋮ The weighted 2-server problem ⋮ Agent searching in a tree and the optimality of iterative deepening ⋮ Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles ⋮ Unnamed Item ⋮ Walking streets faster ⋮ A $$o(n)$$-Competitive Deterministic Algorithm for Online Matching on a Line ⋮ Lower bounds in on-line geometric searching metric searching ⋮ Further connections between contract-scheduling and ray-searching problems ⋮ Querying with Uncertainty ⋮ Searching for a Non-adversarial, Uncooperative Agent on a Cycle ⋮ Going home through an unknown street ⋮ Optimal search for parameters in Monte Carlo simulation for derivative pricing ⋮ Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract) ⋮ Treasure Hunt with Advice ⋮ Limit theorems and structural properties of the cat-and-mouse Markov chain and its generalisations ⋮ Parallel searching in the plane ⋮ Multi-processor search and scheduling problems with setup cost ⋮ The ANTS problem ⋮ Competitive distributed decision-making ⋮ Scheduling search procedures: The wheel of fortune ⋮ A general framework for searching on a line ⋮ God save the queen ⋮ Online search for a hyperplane in high-dimensional Euclidean space ⋮ Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract) ⋮ Online graph exploration: New results on old and new algorithms ⋮ Pebble guided optimal treasure hunt in anonymous graphs ⋮ A \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ Evacuating two robots from multiple unknown exits in a circle ⋮ Evacuating from \(\ell_p\) unit disks in the wireless model ⋮ Strategies for parallel unaware cleaners ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ How many ants does it take to find the food? ⋮ Search Games: A Review ⋮ Learning heuristic functions for large state spaces ⋮ Deterministic treasure hunt in the plane with angular hints ⋮ Online buffer management for transmitting packets with processing cycles ⋮ Searching for an axis-parallel shoreline ⋮ Priority evacuation from a disk: the case of \(n \geq 4\) ⋮ Searching with mobile agents in networks with liars. ⋮ Flood search under the California split rule. ⋮ Online algorithms for searching and exploration in the plane ⋮ Searching and on-line recognition of star-shaped polygons. ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Treasure evacuation with one robot on a disk ⋮ Multi-target ray searching problems ⋮ A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching ⋮ Agent search in uniform b-ary trees: Multiple goals and unequal costs ⋮ Lower bounds for searching robots, some faulty ⋮ The expanding search ratio of a graph ⋮ Online Graph Exploration: New Results on Old and New Algorithms ⋮ Infinite linear programming and online searching with turn cost ⋮ A competitive analysis of algorithms for searching unknown scenes ⋮ Linear search by a pair of distinct-speed robots ⋮ COMPETITIVE COMPLEXITY OF MOBILE ROBOT ON-LINE MOTION PLANNING PROBLEMS ⋮ Search on a line with faulty robots ⋮ Online matching on a line ⋮ On-line path planning in an unknown polygonal environment ⋮ LOWER BOUNDS FOR STREETS AND GENERALIZED STREETS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Online searching with turn cost ⋮ Optimal online-list batch scheduling ⋮ An improved online evacuation strategy from a convex region on grid networks ⋮ Beachcombing on strips and islands ⋮ Searching for a non-adversarial, uncooperative agent on a cycle ⋮ Priority evacuation from a disk: the case of \(n = 1,2,3\) ⋮ Searching on a line: a complete characterization of the optimal solution ⋮ MULTIDIMENSIONAL ONLINE MOTION PLANNING FOR A SPHERICAL ROBOT ⋮ Optimal Distributed Searching in the Plane with and Without Uncertainty ⋮ A General Framework for Searching on a Line ⋮ Reaching a target in the plane with no information ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Classifying the multi robot path finding problem into a quadratic competitive complexity class ⋮ An Improved Online Algorithm for the Traveling Repairperson Problem on a Line ⋮ Linear rendezvous with asymmetric clocks ⋮ Ranking hypotheses to minimize the search cost in probabilistic inference models ⋮ Competitive Searching for a Line on a Line Arrangement. ⋮ Energy Consumption of Group Search on a Line ⋮ Linear Search by a Pair of Distinct-Speed Robots ⋮ Rendezvous in planar environments with obstacles and unknown initial distance ⋮ How to find a point on a line within a fixed distance ⋮ Competitive Algorithms for Layered Graph Traversal ⋮ An improved approximation ratio for the minimum latency problem ⋮ Group search of the plane with faulty robots ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Weighted group search on a line \& implications to the priority evacuation problem ⋮ Optimal robot localization in trees ⋮ The power of a pebble: Exploring and mapping directed graphs ⋮ A correction to: ``Agent searching in a tree and the optimality of iterative deepening ⋮ Walking in Streets with Minimal Sensing ⋮ Walking in streets with minimal sensing ⋮ Graph exploration by energy-sharing mobile agents ⋮ Pebble guided near optimal treasure hunt in anonymous graphs ⋮ Convergecast and broadcast by power-aware mobile agents ⋮ Fast rendezvous on a cycle by agents with different speeds
