Solution Methodologies for the Smallest Enclosing Circle Problem

dc.contributor.author	Xu, Sheng
dc.contributor.author	Freund, Robert M.
dc.contributor.author	Sun, Jie
dc.date.accessioned	2003-12-23T03:14:50Z
dc.date.available	2003-12-23T03:14:50Z
dc.date.issued	2002-01
dc.identifier.uri	http://hdl.handle.net/1721.1/4015
dc.description.abstract	Given a set of circles C = {c₁, ..., cn}on the Euclidean plane with centers {(a₁, b₁), ..., (an, b<sub>n</sub>)}and radii {r₁..., r<n},the smallest enclosing circle (of fixed circles) problem is to ï¬nd the circle of minimum radius that encloses all circles in C. We survey four known approaches for this problem, including a second order cone reformulation, a subgradient approach, a quadratic programming scheme, and a randomized incremental algorithm. For the last algorithm we also give some implementation details. It turns out the quadratic programming scheme outperforms the other three in our computational experiment.	en
dc.description.sponsorship	Singapore-MIT Alliance (SMA)	en
dc.format.extent	175555 bytes
dc.format.mimetype	application/pdf
dc.language.iso	en_US
dc.relation.ispartofseries	High Performance Computation for Engineered Systems (HPCES);
dc.subject	computational geometry	en
dc.subject	optimization	en
dc.title	Solution Methodologies for the Smallest Enclosing Circle Problem	en
dc.type	Article	en