A Voronoi-based method for land-use optimization using semidefinite programming and gradient descent algorithm

ABSTRACT

The land-use optimization involves divisions of land into subregions to obtain spatial configuration of compact subregions and desired connections among them. Computational geometry-based algorithms, such as Voronoi diagram, are known to be efficient and suitable for iterative design processes to achieve land-use optimization. However, such algorithms assume that generating point positions are given as inputs, while we usually do not know the positions in advance. In this study, we propose a method to automatically calculate the suitable point positions. The method uses (1) semidefinite programming to approximate locations while maintaining relative positions among locations; and (2) gradient descent to iteratively update locations subject to area constraints. We apply the proposed framework to a practical case at Chiang Mai University and compare its performance with a benchmark, the differential genetic algorithm. The results show that the proposed method is 28 times faster than the differential genetic algorithm, while the resulting land allocation error is slightly larger than that of the benchmark but still acceptable. Additionally, the output does not contain disconnected areas, as found in all evolutionary computations, and the compactness is almost equal to the maximum possible value.

KEYWORDS:

• Land-use optimization problem
• Voronoi diagram
• SDP-based graph drawing
• gradient descent method
• interactive design

Acknowledgments

We thank Pat Teerasawat from Mitsui Fudosan Asia (Thailand) for his valuable contributions and input provided throughout the study. We also appreciate the editor and reviewers for their valuable comments to improve the manuscript.

Data and codes availability statement

The data and codes that support the findings of this study are available with the identifier(s) at the private link: https://figshare.com/s/fe3c567ff31d698d0ed7.

Disclosure statement

A preliminary version of this work has been published in Chaidee et al. (2017).

Additional information

Funding

We greatly appreciate the financial support this research has received from the Centre of Excellence in Mathematics, The Commission on Higher Education, Thailand, and from Chiang Mai University, Thailand.

Notes on contributors

Vorapong Suppakitpaisarn

Vorapong Suppakitpaisarn is an assistant professor at the Department of Computer Science, The University of Tokyo. His main research areas are cryptographic algorithms and graph/network optimizations. He has co-authored more than 50 refereed articles and has supervised more than 10 graduate students.

Atthaphon Ariyarit

Atthaphon Ariyarit received the B.Eng in Mechanical Engineering from Mahidol University, Thailand, the M.S. in Aeronautics and Astronautics from National Cheng Kung University, Taiwan, and the Ph.D. in Aerospace Engineering from Tokyo Metropolitan University, Japan in 2018. He has been a Lecturer at the School of Mechanical Engineering, Institute of Engineering, Suranaree University of Technology, Thailand since 2019. His current research interests include optimization method, Computation of Fluid Dynamics, and Finite Element Method.

Supanut Chaidee

Supanut Chaidee has been a lecturer at the Department of Mathematics, Faculty of Science, Chiang Mai University, Thailand since 2017. He received the Doctor of Mathematical Sciences from Meiji University, Japan in 2017. His research activities are related to geometric modeling using discrete and computational geometry approaches, especially in Voronoi diagrams.