Return to search

Solution Methodologies for the Smallest Enclosing Circle Problem

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 find 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. / Singapore-MIT Alliance (SMA)

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/4015
Date01 1900
CreatorsXu, Sheng, Freund, Robert M., Sun, Jie
Source SetsM.I.T. Theses and Dissertation
Languageen_US
Detected LanguageEnglish
TypeArticle
Format175555 bytes, application/pdf
RelationHigh Performance Computation for Engineered Systems (HPCES);

Page generated in 0.002 seconds