NDLI: The robot localization problem in two dimensions

Please wait, while we are loading the content...

On the approximation of maximum satisfiability

On likely solutions of a stable matching problem

On playing “Twenty Questions” with a liar

Self-testing polynomial functions efficiently and over rational domains

Deciding finiteness of matrix groups in Las Vegas polynomial time

The probabilistic method

Approximating the minimum weight triangulation

Relative neighborhood graphs in three dimensions

Finding a line transversal of axial objects in three dimensions

Applications of parametric searching in geometric optimization

New algorithms for minimum area k-gons

Tail estimates for the space complexity of randomized incremental algorithms

Load balancing requires &ΩΩ(log*n) expected time

Percolation theory and computing with faulty arrays of processors

Counting networks with arbitrary fan-out

Searching tree structures on a mesh of processors

On parallel complexity of integer linear programming, GCD and the iterated mod function

On the number of Eularian orientations of a graph

Computing minimal spanning subgraphs in linear time

A faster deterministic maximum flow algorithm

A faster algorithm for finding the minimum cut in a graph

Efficient algorithms for the Hitchcock transportation problem

Minimizing capacity violations in a transshipment network

Theoretical and practical aspects of combinatorial problem solving

Generosity helps, or an 11–competitive algorithm for three servers

The competitiveness of on-line assignments

Lower bounds for on-line graph coloring

On efficient unsuccessful search

Strongly competitive algorithms for paging with locality of reference

On-line navigation in a room

Dynamic point location in general subdivisions

The robot localization problem in two dimensions

Optimal link path queries in a simple polygon

An Onlognloglogn algorithm for the on-line closest pair problem

Applications of the fusion tree method to computational geometry and searching

Separation and approximation of polyhedral objects

A general approximation technique for constrained forest problems

Approximating the minimum degree spanning tree to within one from the optimal degree

Improved approximations for the Steiner tree problem

Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity

Sequential and parallel algorithms to find a K5 minor

Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees

Deterministic skip lists

The on-line d-dimensional dictionary problem

Algorithms for subset testing and finding maximal sets

The complexity of heaps

Comparison-sorting and selecting in totally monotone matrices

Finding the repeated median regression line

Strong concentration for Quicksort

(Un)expected behavior of typical suffix trees

Parametric optimization of sequence alignment

Two-dimensional periodicity and its applications

Pattern matching in a digitized image

Improved parallel integer sorting without concurrent writing

The robot localization problem in two dimensions

Content Provider	ACM Digital Library
Author	Motwani, Rajeev Guibas, Leonidas J. Raghavan, Prabhakar
Abstract	We consider the following problem: given a simple polygon P and a star-shaped polygon V, find a point (or the set of points) in P from which the portion of P that is visible is congruent to V. The problem arises in the localization of robots using a range-finder—P is a map of a known environment, V is the portion visible from the robot's position, and the robot must use this information to determine its position in the map. We give a scheme that preprocesses P so that any subsequent query V is answered in optimal time O(m + log n + A), where m and n are the number of vertices in V and P, and A is the number of points in P that are valid answers (the output size). Our technique allows us to trade off smoothly between the query time and the preprocessing time or space. We also devise a data structure for output-sensitive determination of the visibility polygon of a query point inside a polygon P. We then consider a variant of the localization problem in which there is a maximum distance to which the robot can “see”—this is motivated by practical considerations, and we outline a similar solution for this case. We also show that a single localization query V can be answered in time O(mn) with no preprocessing.
Starting Page	259
Ending Page	268
Page Count	10
File Format	PDF
ISBN	089791466X
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1992-09-01
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in