Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Three Paths to Point Placement
verfasst von : Md. Shafiul Alam, Asish Mukhopadhyay
Erschienen in: Algorithms and Discrete Applied Mathematics
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The point placement problem is to determine the positions of a set of
n
distinct
points,
P
= {
p
1
,
p
2
,
p
3
, …,
p
n
}, on a line uniquely, up to translation and reflection, from the fewest possible distance queries between pairs of points. Each distance query corresponds to an edge in a graph, called point placement graph (
ppg
), whose vertex set is
P
. The uniqueness requirement of the placement translates to line rigidity of the
ppg
. In this paper, we show how to construct in 2 rounds a line rigid
ppg
of size 9
n
/7 +
O
(1). This improves the best known result of 4
n
/3 +
O
(1). We also improve the lower bound on 2-round algorithms from 14
n
/13 to 9
n
/8.