AUTOMATIC MST GENERATION FOR EFFICIENT GLOBAL PHYSICAL ACCESS TO CULTURAL SITES

Thodoris Karatasos¹, Evi Papaioannou²*

¹University of Patras, GREECE, tkaratasos@upatras.gr

²University of Patras and CTI “Diophantus”, GREECE, papaioan@ceid.upatras.gr

*Corresponding Author

Abstract

During visits in cultural sites, i.e., archaeological sites, museums, galleries, etc., not all visitors enjoy equal opportunities for easy physical access to all site places and offered facilities. This could be due to particular constraints like lack of escalators or elevators, lack of wireless access to networked facilities during the visit or even difficulty to reach such existing facilities. In order to facilitate physical access to cultural heritage and artistic work and make it accessible to all groups of population, a reasonable approach to correct such inefficiencies could be the automatic design of physical paths joining all places of a cultural site. Lowering the induced construction cost would make such a proposal cost-efficient and thus realistic and worth-implementing. Towards this direction, an important objective consists in suggesting the minimum length of total – escalator or low-emission hot spot - units required to cover the site. Assuming that each cultural site is internally connected, i.e., there is a path between every pair of locations in it, the problem of efficient global access to cultural sites can be abstracted as a well-known problem from graph theory, namely the Minimum Spanning Tree (MST, in short) problem.

In graph theory, a graph, usually denoted as G=(V,E), is composed of a set of vertices, V, and a set of edges, E, where edges connect pairs of (usually distinct) vertices. A predefined function indicates which pairs of vertices are connected by an edge; so, the existence of an edge implies a physical or logical relation between its endpoints, i.e., the vertices it connects. If edges are simple lines without a particular direction then the corresponding graph is called undirected. Edges can also have a number associated with them which is called weight or cost of the edge resulting in edge-weigthed graphs. When there is a path, i.e., a sequence of consecutive edges, between every pair of vertices in a graph, then this graph is said to be connected. A graph is a tree when it is undirected, connected and does not include simple circuits, i.e., paths with no repeated edges that start and end at the same vertex. In graph-theoretic terms, the MST problem can be stated as follows. Given a connected, undirected, edge-weighted graph G=(V,E,w), the objective of the MST problem is to compute a tree of minimum weight containing all vertices of V.

In the context of efficient global physical access to cultural sites, corresponding site locations to vertices and adding an edge between two vertices as long as there is a physical connection between the corresponding site locations makes computing an efficient escalator construction plan equivalent to an instance of the Minimum Spanning Tree problem in the underlying graph. The Minimum Spanning Tree problem can be solved quickly (i.e., in polynomial time in the size of the input) using well-known algorithms from the relevant literature. Following these lines, we designed and implemented an application which automatically computes efficient construction plans (for escalator or low-emission hot spots) for connecting all points of interest in cultural sites. Providing as input an image or a simple photograph of the site in question, the administration of cultural sites can quickly obtain an efficient construction plan which can be used to provide an escalator construction plan of minimum total length. Furthermore, the plan generated by our application also suggests an efficient plan for placing low-emission routers for wireless guiding services and transmission of cultural information to visitors. Looking at the bigger picture, our approach clearly highlights how graph theory and relevant algorithmic solutions can be used to provide efficient practical solutions to a wide range of real world problems.