Minimizing the Diameter of a Spanning Tree for Imprecise Points
dc.contributor.author
Liu, Chih-Hung
dc.contributor.author
Montanari, Sandro
dc.date.accessioned
2023-09-25T12:41:27Z
dc.date.available
2017-06-12T20:11:11Z
dc.date.available
2017-07-18T10:07:09Z
dc.date.available
2018-06-28T11:15:28Z
dc.date.available
2023-09-25T12:41:27Z
dc.date.issued
2018-02
dc.identifier.issn
0178-4617
dc.identifier.issn
1432-0541
dc.identifier.other
10.1007/s00453-017-0292-6
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/129160
dc.identifier.doi
10.3929/ethz-b-000129160
dc.description.abstract
We study the diameter of a spanning tree, i.e., the length of its longest simple path, under the imprecise points model, in which each point is assigned its own occurrence region instead of an exact location. We prove that the minimum diameter of a spanning tree of n points each of which is selected from its respective disk (or axis-parallel square) is polynomial-time computable, contrasting with the fact that minimizing the cost of a spanning tree, i.e. the sum of its edge lengths, for imprecise points is known to be NP-hard. This difference is very interesting since for exact points minimizing the cost seems faster than minimizing the diameter [O(nlogn) versus almost cubic running time]. As the first work regarding the minimum diameter of a spanning tree for imprecise points, our main objective is to investigate essential properties that distinguish the problem from NP-hard instead of minimizing the running time [O(n9) for general disks or O(n6) for unit ones]. Our algorithm mainly utilizes farthest-site Voronoi diagrams for disks and axis-parallel squares, and these diagrams would have their own merits.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
Computational geometry
en_US
dc.subject
Imprecise data
en_US
dc.subject
Minimum diameter spanning trees
en_US
dc.subject
Voronoi diagrams
en_US
dc.title
Minimizing the Diameter of a Spanning Tree for Imprecise Points
en_US
dc.type
Journal Article
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2017-02-23
ethz.journal.title
Algorithmica
ethz.journal.volume
80
en_US
ethz.journal.issue
2
en_US
ethz.journal.abbreviated
Algorithmica
ethz.pages.start
801
en_US
ethz.pages.end
826
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.notes
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.identifier.nebis
010840520
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.relation.isNewVersionOf
20.500.11850/107857
ethz.date.deposited
2017-06-12T20:12:19Z
ethz.source
ECIT
ethz.identifier.importid
imp593655502a63819686
ethz.ecitpid
pub:192119
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-06-28T11:15:31Z
ethz.rosetta.lastUpdated
2024-02-03T04:01:48Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Minimizing%20the%20Diameter%20of%20a%20Spanning%20Tree%20for%20Imprecise%20Points&rft.jtitle=Algorithmica&rft.date=2018-02&rft.volume=80&rft.issue=2&rft.spage=801&rft.epage=826&rft.issn=0178-4617&1432-0541&rft.au=Liu,%20Chih-Hung&Montanari,%20Sandro&rft.genre=article&rft_id=info:doi/10.1007/s00453-017-0292-6&
Files in this item
Publication type
-
Journal Article [127708]