Computing and Informatics

Clustering spatial data is a well-known problem that has been extensively studied. In the real world, there are many physical obstacles such as rivers, lakes, highways, and mountains, whose presence may substantially affect the clustering result. Although many methods have been proposed in previous works, very few have considered physical obstacles and interlinking bridges. Taking these constraints into account during the clustering process is costly, yet modeling the constraints is paramount for good performance. Owing to saturation in existing telephone networks and the ever increasing demand for wire and wireless services, telecommunication engineers are looking at technologies that can deliver sites and satisfy the demand and level of service constraints in an area with and without obstacles. In this paper, we study the problem of clustering in the presence of obstacles to solve the network planning problem. As such, we modified the NetPlan algorithm and developed the COD-NETPLAN (Clustering with Obstructed Distance -- Network Planning) algorithm to solve the problem of 2D and 3D obstacles. We studied the problem of determining the location of the multi service access node in an area with many mountains and rivers. We used a reachability matrix to detect 2D obstacles, and line segment intersection together with geographical information system techniques for 3D obstacles. Experimental results and the subsequent analysis indicate that the COD-NETPLAN algorithm is both efficient and effective.