Efficient Algorithms for Optimal Location Queries in Road Networks Zitong Chen(Sun Yat-Sen University) Yubao Liu(Sun Yat-Sen University) Raymond chi-Wing Wong(Hong Kong University of Science and Technology) Jiamin Xiong(Sun Yat-Sen University) Ganlin Mai (Sun Yat-Sen Universit Cheng Long(Hong Kong University of Science and Technology Presented by raymond Chi-Wing Wong Prepared by Raymond Chi-Wing Wong
1 Efficient Algorithms for Optimal Location Queries in Road Networks Zitong Chen (Sun Yat-Sen University) Yubao Liu (Sun Yat-Sen University) Raymond Chi-Wing Wong (Hong Kong University of Science and Technology) Jiamin Xiong (Sun Yat-Sen University) Ganlin Mai (Sun Yat-Sen University) Cheng Long (Hong Kong University of Science and Technology) Presented by Raymond Chi-Wing Wong Prepared by Raymond Chi-Wing Wong
Outline 1.( Introduction 2. Problem definition 3. Related work 4. Algorithm 5. Empirical Study 6. Conclusion
2 Outline 1. Introduction 2. Problem Definition 3. Related Work 4. Algorithm 5. Empirical Study 6. Conclusion
1 Introduction s=S S21 hospitals C={c1,C2} residential estates C C V5
1. Introduction S = {s1 , s2} C = {c1 , c2} hospitals residential estates v1 v2 v3 v4 v5 v6 c1 s2 c2 s1 3
1 Introduction hospitals Suppose that we want to build a s=S S21 new hospital so that the distance between each residential estate C={c1,C2} residential estates to its nearest hospital is as small as possible earest hospital =S C Where should we set up maximum distance between a residential estate and its nearest 5 hospital 6 nearest hospital=S2 5
1. Introduction S = {s1 , s2} C = {c1 , c2} hospitals residential estates v1 v2 v3 v4 v5 v6 c1 c2 s1 Suppose that we want to build a new hospital so that the distance between each residential estate to its nearest hospital is as small as possible. nearest hospital = s1 nearest hospital = s2 5 2 4 s 5 2 6 maximum distance between a residential estate and its nearest hospital = 6 Where should we set up?
Observation 1: Placing a new hospital at some Placement 16 locations cannot reduce the maximum distance between a residential estate and its nearest hospital hospitals Suppose that we want to build a s=S S21 new hospital so that the distance between each residential estate C={c1,C2} residential estates to its nearest hospital is as small as possible earest hospita C12V2 Placement 1 Suppose that we build a new hospital here maximum distance between a residential estate and its nearest 5 hospital=6 nearest hospital=S,5
1. Introduction S = {s1 , s2} C = {c1 , c2} hospitals residential estates v1 v2 v3 v4 v5 v6 c1 c2 s1 Suppose that we want to build a new hospital so that the distance between each residential estate to its nearest hospital is as small as possible. Suppose that we build a new hospital here nearest hospital = s1 nearest hospital = s2 s 5 2 4 s 5 2 6 maximum distance between a residential estate and its nearest hospital = 6 Placement 1 Observation 1: Placing a new hospital at some locations cannot reduce the maximum distance between a residential estate and its nearest hospital Placement 1 6