An Efficient Algorithm of the Planar 3-Center Problem for a set of the convex position points
The planar 3-center problem for a set S of points given in the plane asks for three congruent circular disks with the minimum radius, whose union can cover all points of S completely. In this paper, we present an O(n2 log3n) time algorithm for a restricted planar 3-center problem in which the given...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
EDP Sciences
2018-01-01
|
| Series: | MATEC Web of Conferences |
| Online Access: | https://doi.org/10.1051/matecconf/201823203022 |
| _version_ | 1818616131868426240 |
|---|---|
| author | Bian Donglai Jiang Bo Cao Zhiying |
| author_facet | Bian Donglai Jiang Bo Cao Zhiying |
| author_sort | Bian Donglai |
| collection | DOAJ |
| description | The planar 3-center problem for a set S of points given in the plane asks for three congruent circular disks with the minimum radius, whose union can cover all points of S completely. In this paper, we present an O(n2 log3n) time algorithm for a restricted planar 3-center problem in which the given points are in the convex positions , i.e. The given points are the vertices of a convex polygon exactly. |
| first_indexed | 2024-12-16T16:44:56Z |
| format | Article |
| id | doaj.art-2c06f45dcc874cd2a83d2183726f23db |
| institution | Directory Open Access Journal |
| issn | 2261-236X |
| language | English |
| last_indexed | 2024-12-16T16:44:56Z |
| publishDate | 2018-01-01 |
| publisher | EDP Sciences |
| record_format | Article |
| series | MATEC Web of Conferences |
| spelling | doaj.art-2c06f45dcc874cd2a83d2183726f23db2022-12-21T22:24:13ZengEDP SciencesMATEC Web of Conferences2261-236X2018-01-012320302210.1051/matecconf/201823203022matecconf_eitce2018_03022An Efficient Algorithm of the Planar 3-Center Problem for a set of the convex position pointsBian Donglai0Jiang Bo1Cao Zhiying2School of Information Science and Technology, Dalian Maritime UniversitySchool of Information Science and Technology, Dalian Maritime UniversitySchool of Information Science and Technology, Dalian Maritime UniversityThe planar 3-center problem for a set S of points given in the plane asks for three congruent circular disks with the minimum radius, whose union can cover all points of S completely. In this paper, we present an O(n2 log3n) time algorithm for a restricted planar 3-center problem in which the given points are in the convex positions , i.e. The given points are the vertices of a convex polygon exactly.https://doi.org/10.1051/matecconf/201823203022 |
| spellingShingle | Bian Donglai Jiang Bo Cao Zhiying An Efficient Algorithm of the Planar 3-Center Problem for a set of the convex position points MATEC Web of Conferences |
| title | An Efficient Algorithm of the Planar 3-Center Problem for a set of the convex position points |
| title_full | An Efficient Algorithm of the Planar 3-Center Problem for a set of the convex position points |
| title_fullStr | An Efficient Algorithm of the Planar 3-Center Problem for a set of the convex position points |
| title_full_unstemmed | An Efficient Algorithm of the Planar 3-Center Problem for a set of the convex position points |
| title_short | An Efficient Algorithm of the Planar 3-Center Problem for a set of the convex position points |
| title_sort | efficient algorithm of the planar 3 center problem for a set of the convex position points |
| url | https://doi.org/10.1051/matecconf/201823203022 |
| work_keys_str_mv | AT biandonglai anefficientalgorithmoftheplanar3centerproblemforasetoftheconvexpositionpoints AT jiangbo anefficientalgorithmoftheplanar3centerproblemforasetoftheconvexpositionpoints AT caozhiying anefficientalgorithmoftheplanar3centerproblemforasetoftheconvexpositionpoints AT biandonglai efficientalgorithmoftheplanar3centerproblemforasetoftheconvexpositionpoints AT jiangbo efficientalgorithmoftheplanar3centerproblemforasetoftheconvexpositionpoints AT caozhiying efficientalgorithmoftheplanar3centerproblemforasetoftheconvexpositionpoints |