Assistant Professor Junqiu Wei from the School of Computer Science and Engineering, Faculty of Innovation Engineering, Macau University of Science and Technology (MUST), published a research paper entitled "Constrained Shortest Path Finding on Terrain Surfaces" as the first author at the top international academic conference ACM Conference on Management of Data (SIGMOD), 2026. He was invited to present the paper at the conference on 4th June 2026. This paper was a collaborative effort involving MUST, the Shenzhen Institute of Computing Science, and Beijing Institute of Technology (Zhuhai Campus).

Assistant Professor Wei gave a presentation at the SIGMOD

The SIGMOD is one of the most influential international academic conferences in the fields of databases, data mining, and data science, and is recommended as a Category A international academic conference by the China Computer Federation (CCF). This paper, accepted for SIGMOD 2026, represents only a small percentage of accepted papers, highlighting the innovativeness and academic value of this research. This is also the first research paper published at SIGMOD by MUST as the first affiliated institution, demonstrating MUST's outstanding research strength, innovation capabilities, and international competitiveness in the field of data science.

With the continuous development of Geographic Information Systems (GIS), computational geometry, and computer graphics technologies, digital terrain surface data has become ubiquitous, finding applications in industrial simulation software, military simulations, medical imaging, and virtual reality games. In recent years, the rise of the metaverse and spatial intelligence has broadened the application of this data, playing a crucial role in scenarios such as virtual environment within the metaverse and spatial intelligence. In academia, top international universities such as the University of Maryland, the University of Southern California, the University of Queensland, the Hong Kong University of Science and Technology, Nanyang Technological University, and Aalborg University have all conducted pioneering research on terrain data.

Digital Terrain Surface

Digital terrain data is collected through field surveys of the real surface and then constructed into a 3D terrain model by stitching together countless triangular facets. The real ground surface is not flat but features undulations and elevations. On such a rugged terrain surface, the shortest distance between two locations when traveling along the ground is called the "geodesic distance." The research team has now proposed a new problem in terrain path querying, named “Constrained Shortest Path on Terrain Surface.”

The biggest challenge in traditional terrain path calculations is the complex structure of real terrain surfaces and the massive volume of data involved. If calculations are performed directly on the complete undulating terrain, the process becomes extremely cumbersome and time-consuming, while also consuming large amounts of computer memory. It is very difficult to quickly and accurately compute the shortest surface path that meets multiple constraint conditions, making it hard to balance computational accuracy and efficiency.

Path Finding Based on Spanning Graph

To solve the above challenges, Professor Wei’s research team developed a brand-new, high-precision original algorithm. First, instead of directly processing the vast and complex raw terrain data, the team extracts key information from the massive dataset to construct an extremely simplified and lightweight " Spanning Graph " network. This network has a very small number of edges — only a fixed multiple of the number of target points — resulting in a significantly reduced data size. Nevertheless, it can accurately restore and simulate the true geodesic distance between any two points on the terrain surface, with nearly no loss in precision. Second, relying on this lightweight generated graph network and combining it with the "Minimum Spanning Tree" algorithm, the system can rapidly compute and sort the optimal visiting order for all target locations, ultimately reconstructing the shortest surface path on the original real terrain that satisfies all given constraints.

The newly developed algorithm offers extremely high practicality and delivers remarkable breakthroughs. Compared with traditional standard methods, the new technology significantly improves computation speed while maintaining high accuracy, and greatly reduces computer memory usage. Overall performance is several orders of magnitude higher than traditional approaches.

The publication of the research finding demonstrates Macau University of Science and Technology's continuous innovation capabilities in data science research, as well as its international competitiveness in cutting-edge areas such as spatial big data and spatial intelligence. In the future, Macau University of Science and Technology will continue to support cutting-edge scientific research, promote the deep integration of data science, spatial intelligence, and smart cities, and contribute more to global technological innovation and the development of a smart society.

The research paper can be found via the link: https://dl.acm.org/doi/abs/10.1145/3802031