nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

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

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

Erschienen in: Transactions on Computational Science XXXIII

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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)].

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel The Refutation of Amdahl’s Law and Its Variants

Nächstes Kapitel Neighbourhood Graphs and Locally Minimal Triangulations

Damaschke, P.: Randomized vs. deterministic distance query strategies for point location on the line. Discrete Appl. Math. 154(3), 478–484 (2006)MathSciNetCrossRef

Damaschke, P.: Point placement on the line by distance data. Discrete Appl. Math. 127(1), 53–62 (2003)MathSciNetCrossRef

Chin, F.Y.L., Leung, H.C.M., Sung, W.K., Yiu, S.M.: The point placement problem on a line-improved bounds for pairwise distance queries. In: Giancarlo, R., Hannenhalli, S. (eds.) WABI 2007. LNCS, vol. 4645, pp. 372–382. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74126-8_35CrossRef

Alam, M.S., Mukhopadhyay, A.: More on generalized jewels and the point placement problem. J. Graph Algorithms Appl. 18(1), 133–173 (2014)MathSciNetCrossRef

Alam, M.S., Mukhopadhyay, A.: Three paths to point placement. In: Ganguly, S., Krishnamurti, R. (eds.) CALDAM 2015. LNCS, vol. 8959, pp. 33–44. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-14974-5_4CrossRef

Aspnes, J., et al.: A theory of network localization. IEEE Trans. Mobile Comput. 5(12), 1663–1678 (2006)CrossRef

Biswas, P., Liang, T., Wang, T., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. TOSN 2(2), 188–220 (2006)CrossRef

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

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.

Ellis, R., Lay, D.: Rank-preserving extensions of band matrices. Linear Multilinear Algebra 26, 147–179 (1990)MathSciNetCrossRef

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

Titel: A Distance Matrix Completion Approach to 1-Round Algorithms for Point Placement in the Plane
verfasst von: Md. Zamilur Rahman
Udayamoorthy Navaneetha Krishnan
Cory Jeane
Asish Mukhopadhyay
Yash P. Aneja
Verlag: Springer Berlin Heidelberg
Buch: Transactions on Computational Science XXXIII
Print ISBN: 978-3-662-58038-7

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"