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 ï¬nd the circle of minimum radius that encloses all circles in C. We survey four known...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/4015 |
| _version_ | 1826192169038249984 |
|---|---|
| author | Xu, Sheng Freund, Robert M. Sun, Jie |
| author_facet | Xu, Sheng Freund, Robert M. Sun, Jie |
| author_sort | Xu, Sheng |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:07:16Z |
| format | Article |
| id | mit-1721.1/4015 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:07:16Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/40152019-04-10T18:39:46Z Solution Methodologies for the Smallest Enclosing Circle Problem Xu, Sheng Freund, Robert M. Sun, Jie computational geometry optimization 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. Singapore-MIT Alliance (SMA) 2003-12-23T03:14:50Z 2003-12-23T03:14:50Z 2002-01 Article http://hdl.handle.net/1721.1/4015 en_US High Performance Computation for Engineered Systems (HPCES); 175555 bytes application/pdf application/pdf |
| spellingShingle | computational geometry optimization Xu, Sheng Freund, Robert M. Sun, Jie Solution Methodologies for the Smallest Enclosing Circle Problem |
| title | Solution Methodologies for the Smallest Enclosing Circle Problem |
| title_full | Solution Methodologies for the Smallest Enclosing Circle Problem |
| title_fullStr | Solution Methodologies for the Smallest Enclosing Circle Problem |
| title_full_unstemmed | Solution Methodologies for the Smallest Enclosing Circle Problem |
| title_short | Solution Methodologies for the Smallest Enclosing Circle Problem |
| title_sort | solution methodologies for the smallest enclosing circle problem |
| topic | computational geometry optimization |
| url | http://hdl.handle.net/1721.1/4015 |
| work_keys_str_mv | AT xusheng solutionmethodologiesforthesmallestenclosingcircleproblem AT freundrobertm solutionmethodologiesforthesmallestenclosingcircleproblem AT sunjie solutionmethodologiesforthesmallestenclosingcircleproblem |