Planar Emulators for Monge Matrices

Hsien-Chih Chang; Tim A.E. Ophelders

Planar Emulators for Monge Matrices

Hsien-Chih Chang, Tim A.E. Ophelders

Applied Geometric Algorithms

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

3 Citaten (Scopus)

Samenvatting

We constructively show that any cyclic Monge distance matrix can be represented as the graph distances between vertices on the outer face of a planar graph. The structure of the planar graph depends only on the number of rows of the matrix, and the weight of each edge is a fixed linear combination of constantly many matrix entries. We also show that the size of our constructed graph is worst-case optimal among all planar graphs.

Originele taal-2	Engels
Titel	Proc. 32nd Canadian Conference on Computational Geometry (CCCG)
Pagina's	141-147
Aantal pagina's	7
Status	Gepubliceerd - 2020

Toegang tot document

https://hcsoso.github.io/papers/pdf/monge.pdfLicentie: Onbepaald

Andere bestanden en links

Citeer dit

@inproceedings{0b0b67621b6340e1b3c3912ad507bcd8,

title = "Planar Emulators for Monge Matrices",

abstract = "We constructively show that any cyclic Monge distance matrix can be represented as the graph distances between vertices on the outer face of a planar graph. The structure of the planar graph depends only on the number of rows of the matrix, and the weight of each edge is a fixed linear combination of constantly many matrix entries. We also show that the size of our constructed graph is worst-case optimal among all planar graphs.",

author = "Hsien-Chih Chang and Ophelders, {Tim A.E.}",

year = "2020",

language = "English",

pages = "141--147",

booktitle = "Proc. 32nd Canadian Conference on Computational Geometry (CCCG)",

}

TY - GEN

T1 - Planar Emulators for Monge Matrices

AU - Chang, Hsien-Chih

AU - Ophelders, Tim A.E.

PY - 2020

Y1 - 2020

N2 - We constructively show that any cyclic Monge distance matrix can be represented as the graph distances between vertices on the outer face of a planar graph. The structure of the planar graph depends only on the number of rows of the matrix, and the weight of each edge is a fixed linear combination of constantly many matrix entries. We also show that the size of our constructed graph is worst-case optimal among all planar graphs.

AB - We constructively show that any cyclic Monge distance matrix can be represented as the graph distances between vertices on the outer face of a planar graph. The structure of the planar graph depends only on the number of rows of the matrix, and the weight of each edge is a fixed linear combination of constantly many matrix entries. We also show that the size of our constructed graph is worst-case optimal among all planar graphs.

UR - http://vga.usask.ca/cccg2020/papers/Proceedings.pdf

UR - http://www.scopus.com/inward/record.url?scp=85125031152&partnerID=8YFLogxK

M3 - Conference contribution

SP - 141

EP - 147

BT - Proc. 32nd Canadian Conference on Computational Geometry (CCCG)

ER -

Planar Emulators for Monge Matrices

Samenvatting

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit