A Computational Method for Optimizing the Shape and Location of a Polygon on a Plane

Authors: Shiode, Narushige¹; Okabe, Atsuyuki²

Source: International Transactions in Operational Research, Volume 8, Number 5, September 2001 , pp. 547-559(13)

Buy & download fulltext article:

Price: $48.00 plus tax (Refund Policy)

Abstract:

This study applies the concept of the Voronoi diagram to a simultaneous search for the optimal shape and location of a polygon. Suppose that an area-like facility is contained in a finite two-dimensional uniform region. The objective of our study is to optimize the shape and location of the facility (polygon) in terms of the mini-sum distance from all the surrounding points. When the mini-sum distance is minimized, the polygon forms a star-shaped polygon at the center, and when maximized, it verges alongside the edge of the region. The results are represented by an approximate value of local optima obtained by replacing the boundary of the polygon with points. We justify the results by examining the difference between the value obtained from a line Voronoi diagram and that generated from points.

Keywords: approximation precision; locational optimization; mini-sum distance; non-linear programming; optimization of shape; Voronoi diagram

Document Type: Original article

DOI: http://dx.doi.org/10.1111/1475-3995.00332

Affiliations: 1: Centre for Advanced Spatial Analysis, University College London, UK, 2: Center for Spatial Information Science, University of Tokyo, Japan

Publication date: 2001-09-01