Building bridges between convex regions

Cited 1 time in webofscience Cited 0 time in scopus
  • Hit : 958
  • Download : 460
In the Euclidean traveling salesman and buyers problem (TSBP), we are given a set of convex regions in d-dimensional space, and we wish to find a minimum-cost tour that visits all the regions. The cost of a tour depends on the length of the tour itself and on the distance that buyers within each region need to travel to meet the salesman. We show that constant-factor approximations to the TSBP and several similar problems can be obtained by visiting the centers of the smallest enclosing spheres of the regions. (C) 2002 Elsevier Science B.V. All rights reserved.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2003-05
Language
English
Article Type
Article; Proceedings Paper
Keywords

POLYGONS; ALGORITHMS

Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.25, pp.161 - 170

ISSN
0925-7721
DOI
10.1016/S0925-7721(02)00135-9
URI
http://hdl.handle.net/10203/310
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 1 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0