Determining Fire Station Location Using Convex Hull

The aim of this paper is to determine a location of fire station in South Kuta using convex hull and Dijkstra algorithm. The location was obtained using polygon convex approximation, where centroid of polygon is chosen as the best candidate. Housing coordinate points were used as sample points to construct convex hull using Graham Scan’s. The centroid of convex hull is the best candidate point to place the station in order to make Euclidean distances can be minimized. Further, to minimize response time, Dijkstra algorithm used to find shortest route from candidate point of fire station to every fire-prone points. The obtained location will be compared with the location of existing fire station to examine its performance. Keywords: Convex hull; Dijkstra algorithm; fire station; Kuta; minimax facility location.