A Study on Voronoi Diagrams with Obstacles in the Architectural and Urban Space

本研究分为两个部分，第一部分是有障碍物Voronoi图的构造方法，第二部分是将该方法应用于实际的建筑和城市空间中，展示了该方法的效率和效益，第一部分提出了一种简单实用的计算机算法来构造二维有障碍物Voronoi图，使用由许多随机顶点组成的Delaunay网络的最短路径距离，我们称之为rDn。该方法通过测量rDn中的最短路径距离作为绕行距离，为有障碍物的Voronoi图提供了一个近似解。通过计算机实验验证了rDn的最短路径距离与欧几里得距离之比的各向同性和稳定性。在简单情况下，通过与精确解的比较，证明了近似解的可靠性，并通过求解一个具有自由形状障碍物的问题，证明了该方法的有效性。第二部分介绍了带障碍物的Voronoi图的构造和应用。通过应用该模型，我们分析了自动体外除颤器（AED）在日本东京上野公园周围的域，并指出了一个更有效的AED位置，包括必要的时间，为救援人员和他或她的助手都发生在附近的心脏骤停（SCA）的受害者，以获得AED避免各种障碍：池塘，建筑物，植物，围栏，在公园。在指出AED的当前位置后，我们提出了一个新的位置计划，即在没有AED的公园内的公共设施中放置额外的AED，这将使平均最短路径距离从343米提高到119米，相当于提高了近18%的生存率。

This research consists of two parts, the first part is the methodology of the Voronoi diagrams with obstacles, and the second one is the application of the method to the actual architectural and urban space, which shows the efficiency and benefit by this method.In the first part, we propose a method for constructing Voronoi diagrams with two-dimensional obstacles by a simple and practical computer algorithm, using the shortest-path distance of a Delaunay network of many random vertices, which we termed as rDn. By measuring the shortest-path distance of the rDn for the detour distance, this method provides an approximate solution for the Voronoi diagrams with obstacles. We verify the isotropy and stability of the ratio of the shortest-path distance of the rDn and the Euclid distance by a computer experiment. We then show the reliability of the approximate solution by comparing with the exact solution in a simple case, and the effectiveness of this method by solving a sample problem with free shaped obstacles.The second part describes the construction and application of Voronoi diagrams with obstacles. By applying the model, we analyzed the domain of Automated External Defibrillators (AED) around Ueno Park in Tokyo, Japan, and indicated a more efficient AED location by including the necessary time for the rescuer and his or her helper both of whom happened to be near the victim of Sudden Cardiac Arrest (SCA), to get an AED avoiding various obstacles: pond, building, planting, fence, in the park. After indicating the current location of AEDs, we proposed a new location plan with additional AEDs placed in public facilities in the park with no AED that will improve the average shortest-path distance from 343m to 119m, which is equivalent to almost 18% improvement in survival rate.