Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolygon Exploration with Time-Discrete Vision
59
0
0.0
(
0
)
Added by
Sandor P. Fekete
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained in practical importance. However, real-life laser scanning of useful accuracy does not allow the robot to scan continuously while in motion; instead, it has to stop each time it surveys its environment. This requirement was studied by Fekete, Klein and Nuechter for the subproblem of looking around a corner, but until now has not been considered in an online setting for whole polygonal regions. We give the first algorithmic results for this important algorithmic problem that combines stationary art gallery-type aspects with watchman-type issues in an online scenario: We demonstrate that even for orthoconvex polygons, a competitive strategy can be achieved only for limited aspect ratio A (the ratio of the maximum and minimum edge length of the polygon), i.e., for a given lower bound on the size of an edge; we give a matching upper bound by providing an O(log A)-competitive strategy for simple rectilinear polygons, using the assumption that each edge of the polygon has to be fully visible from some scan point.
rate research
Read More
Suppose an escaping player moves continuously at maximum speed 1 in the interior of a region, while a pursuing player moves continuously at maximum speed $r$ outside the region. For what $r$ can the first player escape the region, that is, reach the boundary a positive distance away from the pursuing player, assuming optimal play by both players? We formalize a model for this infinitesimally alternating 2-player game that we prove has a unique winner in any region with locally rectifiable boundary, avoiding pathological behaviors (where both players can have winning strategies) previously identified for pursuit-evasion games such as the Lion and Man problem in certain metric spaces. For some regions, including both equilateral triangle and square, we give exact results for the critical speed ratio, above which the pursuing player can win and below which the escaping player can win (and at which the pursuing player can win). For simple polygons, we give a simple formula and polynomial-time algorithm that is guaranteed to give a 10.89898-approximation to the critical speed ratio, and we give a pseudopolynomial-time approximation scheme for arbitrarily approximating the critical speed ratio. On the negative side, we prove NP-hardness of the problem for polyhedral domains in 3D, and prove stronger results (PSPACE-hardness and NP-hardness even to approximate) for generalizations to multiple escaping and pursuing players.
We study the geodesic Voronoi diagram of a set $S$ of $n$ linearly moving sites inside a static simple polygon $P$ with $m$ vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector KDS handles each event in $O(log m)$ time, and our Voronoi center handles each event in $O(log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
We construct a family of 17 disjoint axis-parallel line segments in the plane that do not admit a circumscribing polygon.
Deciding whether a family of disjoint line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard.
Researchers and robotic development groups have recently started paying special attention to autonomous mobile robot navigation in indoor environments using vision sensors. The required data is provided for robot navigation and object detection using a camera as a sensor. The aim of the project is to construct a mobile robot that has integrated vision system capability used by a webcam to locate, track and follow a moving object. To achieve this task, multiple image processing algorithms are implemented and processed in real-time. A mini-laptop was used for collecting the necessary data to be sent to a PIC microcontroller that turns the processes of data obtained to provide the robots proper orientation. A vision system can be utilized in object recognition for robot control applications. The results demonstrate that the proposed mobile robot can be successfully operated through a webcam that detects the object and distinguishes a tennis ball based on its color and shape.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
