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)
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/4015 |
| Date | 01 1900 |
| Creators | Xu, Sheng, Freund, Robert M., Sun, Jie |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | en_US |
| Detected Language | English |
| Type | Article |
| Format | 175555 bytes, application/pdf |
| Relation | High Performance Computation for Engineered Systems (HPCES); |
Page generated in 0.002 seconds