A Computational Method for Optimizing the Shape and Location of a Polygon on a Plane
Authors: Shiode, Narushige1; Okabe, Atsuyuki2
Source: International Transactions in Operational Research, Volume 8, Number 5, September 2001 , pp. 547-559(13)
Publisher: Blackwell Publishing
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
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: 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
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
Click here for Page Help