Efficient Algorithms for Optimal Location Queries in Road Networks

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

Observation 1: Placing a new hospital at some Placement 16 locations cannot reduce the maximum distance between a residential estate and its nearest Placement 2 hospital Observation 2: Placing a new hospital at some locations can reduce the maximum distance between a residential estate and its nearest Suppose that we want to build a hospital new hospital so that the distance between each residential estate C=Ct C23 residential estates to its nearest hospital is as small as possible nearest hospital =s C Placement 2 Suppose that we build a new hospital here maximum distance between a residential estate and its nearest 5 2V5 hospital =5 nearest hospital =s 4

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 s 65 s 4 maximum distance between a residential estate and its nearest hospital = 65 2 3 2 2 Placement 2 Observation 1: Placing a new hospital at some locations cannot reduce the maximum distance between a residential estate and its nearest hospital Observation 2: Placing a new hospital at some locations can reduce the maximum distance between a residential estate and its nearest hospital Placement 1 6 Placement 2 5

Observation 1: Placing a new hospital at some Placement 16 locations cannot reduce the maximum distance between a residential estate and its nearest Placement 2 hospita Placement34.5 Observation 2: Placing a new hospital at some locations can reduce the maximum distance Which placement is better? between a residential estate and its nearest uppose thiat vve Placement 3 hospital new hospital so that tri u between each residential estate C=Ct C23 residential estates to its nearest hospital is as small as possible nearest hospital=s4.5 C Placement 3 Suppose that we build a ney 2.5 hospital here 2.5 maximum distance between a residential estate and its nearest 5 2V5 hospital =4.5 nearest hospital =s4.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 s 64.5 s 4.5 maximum distance between a residential estate and its nearest hospital = 64.5 2 2.5 2 2.5 Placement 3 Observation 1: Placing a new hospital at some locations cannot reduce the maximum distance between a residential estate and its nearest hospital Observation 2: Placing a new hospital at some locations can reduce the maximum distance between a residential estate and its nearest hospital Placement 1 6 Placement 2 5 Placement 3 4.5 Which placement is better? Placement 3

Problem: We want to find a Optimal location query location for the new hospital so that the maximum distance The Min Max Query uction its nearest hospital is minimized Emergency applications (such as hospitals, police Suppose that we want to build a stations and fire stations) new hospital so that the distance between each residential estate C={c1,C2 residential estates to its nearest hospital is as small possible earest hospital=s4.5 C Placement 3 Suppose that we build a new 2.5 hospital here 2.5 maximum distance between a idential estate and its nearest 5 2V5 hospital =4.5 nearest hospital =s4.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 s 64.5 s 4.5 maximum distance between a residential estate and its nearest hospital = 64.5 2 2.5 2 2.5 Placement 3 Problem: We want to find a location for the new hospital so that the maximum distance between a residential estate and its nearest hospital is minimized. Optimal location query The MinMax Query Emergency applications (such as hospitals, police stations and fire stations)

Outline 1. Introduction 2 Problem definition 3. Related work 4. Algorithm 5. Empirical Study 6. Conclusion

9 Outline 1. Introduction 2. Problem Definition 3. Related Work 4. Algorithm 5. Empirical Study 6. Conclusion

Problem: We want to find a location for the new hospital so that the maximum distance 2. Problem Defin between a residential estate and its nearest hospital is minimized After we define the problem, we need to give some concepts

2. Problem Definition ◼ After we define the problem, we need to give some concepts 10 Problem: We want to find a location for the new hospital so that the maximum distance between a residential estate and its nearest hospital is minimized