Paper Info
Title
Randomized vs. deterministic distance query strategies for point location on the line
Abstract
Suppose that n points are located at n mutually distinct but unknown positions on the line, and we can measure their pairwise distances. How many measurements are needed to determine their relative positions uniquely? The problem is motivated by DNA mapping techniques based on pairwise distance measures. It is also interesting by itself for its own and surprisingly deep. Continuing our earlier work on this problem, we give a simple randomized two-round strategy that needs, with high probability, only (1 + o(1))n measurements. We show that deterministic strategies cannot manage the task in two rounds with (1 + o(1))n measurements in the worst case. We improve an earlier deterministic bound to roughly 4n/3 measurements.
Year
DOI
Venue
2006
10.1016/j.dam.2005.07.014
Discrete Applied Mathematics
Keywords
Field
DocType
dna mapping,n measurement,randomized strategy,deterministic distance query strategy,high probability,graph rigidity,learning by queries,deterministic strategy,n point,pairwise distance,simple randomized two-round strategy,earlier work,relative position,point location,dna mapping technique,pairwise distance measure
Pairwise comparison,Distance measurement,Discrete mathematics,Combinatorics,Point location,Randomized strategy,Probability distribution,Graph rigidity,Mathematics,Distance measures
Journal
Volume
Issue
ISSN
154
3
Discrete Applied Mathematics
Citations 
PageRank 
References 
3
0.54
6
Authors
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99