Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Delta-Diagram Based Synthesis for Cross Layer Optimization Modeling of IoT Read chapter Read first chapter

2018 | OriginalPaper | Chapter

A Distance Matrix Completion Approach to 1-Round Algorithms for Point Placement in the Plane

Authors : Md. Zamilur Rahman, Udayamoorthy Navaneetha Krishnan, Cory Jeane, Asish Mukhopadhyay, Yash P. Aneja

Published in: Transactions on Computational Science XXXIII

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper we propose a 1-round algorithm for approximate point placement in the plane in an adversarial model. The distance query graph presented to the adversary is chordal. The remaining distances are determined using a distance matrix completion algorithm for chordal graphs, based on a result by Bakonyi and Johnson [SIAM Journal on Matrix Analysis and Applications 16 (1995)]. The layout of the points is determined from the complete distance matrix in two ways: using the traditional Young-Householder approach as well as a Stochastic Proximity Embedding (SPE) method due to Agrafiotis [Journal of Computational Chemistry 24 (2003)].

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter The Refutation of Amdahl’s Law and Its Variants
next chapter Neighbourhood Graphs and Locally Minimal Triangulations
Literature
1.
Damaschke, P.: Randomized vs. deterministic distance query strategies for point location on the line. Discrete Appl. Math. 154(3), 478–484 (2006)MathSciNetCrossRef
2.
3.
4.
Alam, M.S., Mukhopadhyay, A.: More on generalized jewels and the point placement problem. J. Graph Algorithms Appl. 18(1), 133–173 (2014)MathSciNetCrossRef
5.
6.
Aspnes, J., et al.: A theory of network localization. IEEE Trans. Mobile Comput. 5(12), 1663–1678 (2006)CrossRef
7.
Biswas, P., Liang, T., Wang, T., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. TOSN 2(2), 188–220 (2006)CrossRef
8.
Schoenberg, I.J.: Remarks to Maurice Fretchet’s article “sur la definition axiomatique d’une classe d’espace distancis vectoriellement applicable sur l’espace de Hilbert". Ann. Math. 36(3), 724–731 (1935)MathSciNetCrossRef
9.
Young, G., Householder, A.S.: Discussion of a set of points in terms of their mutual distances. Psychometrika 3(1), 19–22 (1938)CrossRef
10.
Mukhopadhyay, A., Sarker, P.K., Kannan, K.K.V.: Point placement algorithms: an experimental study. Int. J. Exp. Algorithms 6(1), 1–13 (2016)
11.
Bakonyi, M., Johnson, C.R.: The euclidian distance matrix completion problem. SIAM J. Matrix Anal. Appl. 16(2), 646–654 (1995)MathSciNetCrossRef
12.
Agrafiotis, D.K.: Stochastic proximity embedding. J. Comput. Chem. 24(10), 1215–1221 (2003)CrossRef
13.
Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266–283 (1976)MathSciNetCrossRef
14.
Grone, R., Johnson, C.R., Sa, E.M., Wolkowicz, H.: Positive definite completions of partial hermitian matrices. Linear Algebra Appl. 58, 109–124 (1984)MathSciNetCrossRef
15.
Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)CrossRef
16.
17.
Kabsch, W.: A solution for the best rotation to relate two sets of vectors. Acta Crystallogr. A 32(5), 922–923 (1976)CrossRef
18.
Markenzon, L., Vernet, O., Araujo, L.H.: Two methods for the generation of chordal graphs. Ann. OR 157(1), 47–60 (2008)MathSciNetCrossRef
Metadata
Title
A Distance Matrix Completion Approach to 1-Round Algorithms for Point Placement in the Plane
Authors
Md. Zamilur Rahman
Udayamoorthy Navaneetha Krishnan
Cory Jeane
Asish Mukhopadhyay
Yash P. Aneja
Copyright Year
2018
Publisher
Springer Berlin Heidelberg
Book
Transactions on Computational Science XXXIII

Print ISBN: 978-3-662-58038-7

Electronic ISBN: 978-3-662-58039-4

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-662-58039-4_6

Premium Partner

    Image Credits