NDLI: A probabilistic algorithm for the post office problem

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

A simple parallel algorithm for the maximal independent set problem

The two-processor scheduling problem is in R-NC

Constructing a perfect matching is in random NC

A parallel algorithm for the maximal path problem

The parallel complexity of exponentiating polynomials over finite fields

One, two, three . . . infinity: lower bounds for parallel computation

Tradeoffs for VLSI models with subpolynomial delay

Algorithms for routing and testing routability of planar VLSI layouts

Provably good routing in graphs: regular arrays

Expanders obtained from affine transformations

Expanders, sorting in rounds and superconcentrators of limited depth

White pebbles help

Stable prehension with three fingers

Riemann hypothesis and finding roots over finite fields

Computing with polynomials given by straight-line programs I: greatest common divisors

Efficient parallel solution of linear systems

Polynomial time solutions of some problems of computational algebra

A general approach to d-dimensional geometric queries

Space-time tradeoffs for orthogonal range queries

A probabilistic algorithm for the post office problem

A linear algorithm for finding dominators in flow graphs and related problems

Multicommodity flows in planar undirected graphs and shortest paths

The effect of updates in binary search trees

Finding the median requires 2n comparisons

Self-organizing sequential search and Hilbert's inequalities

On the expected behavior of disjoint set union algorithms

Concurrent dynamic logic

Improved upper and lower bounds for modal logics of programs

Transition systems, infinitary languages and the semantics of uniform concurrency

Provable isomorphisms and domain equations in models of typed languages

Equational theories and database constraints

The polynomial hierarchy and fragments of bounded arithmetic

The knowledge complexity of interactive proof-systems

An internal semantics for modal logic

An O(lg n) expected rounds randomized Byzantine generals protocol

Fault tolerance of minimal path routings in a network

The distributed firing squad problem

Optimal precision in the presence of uncertainty

The cryptographic security of truncated linearly related variables

One-way functions and pseudorandom generators

Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources

On the stability of the Ethernet

A simple three-dimensional real-time cellular array

Doubly lexical orderings of matrices

The complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems

Fast algorithms for n-dimensional restrictions of hard problems

Trading group theory for randomness

An algorithm for finding Hamilton cycles in random graphs

Compression and ranking

The complexity of backtrack searches

NP is as easy as detecting unique solutions

Are search and decision programs computationally equivalent?

Dual integer linear programs and the relationship between their optima

A probabilistic algorithm for the post office problem

Content Provider	ACM Digital Library
Author	Clarkson, K
Abstract	The post office problem is the following: points in d-dimensional space, so that given an arbitrary point p, the closest points in S to p can be found quickly.We consider the case of this problem where the Euclidean norm is the measure of distance. The previous best algorithm for this problem for d>2 requires &Ogr;(n2d+1) preprocessing time to build a data structure allowing an &Ogr;(log n query time. We will show that a data structure can be built in expected &Ogr;(n(d-1)(1+k)) time, for any fixed k;>&Ogr;, so that closest-point queries can be answered in &Ogr;(log n) worstcase time. (The constant factors depend on d and k.) The algorithm employs random sampling, so the expected time holds for any set of points. A variant of this algorithm (for the variant problem where only one closest point of S to the query point is desired) requires &Ogr;(n⌈d/2⌉) &ogr;(n⌈d/2⌉) preprocessing time for &ogr;(nt) worst-case query time, for any fixed ε>0. These results approach the &OHgr;(n⌈d/2⌉) preprocessing time required for any algorithm constructing the Voronoi diagram of the input points. Implementation of these algorithms requires not too much more than a random sampling procedure and a procedure for constructing the Voronoi diagram of that random sample.
Starting Page	175
Ending Page	184
Page Count	10
File Format	PDF
ISBN	0897911512
DOI	10.1145/22145.22165
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1985-12-01
Publisher Place	New York
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