A geometric proof of the combinatorial bounds for the number of optimal solutions for the Euclidean 2-center problem |
| |
| Authors: | Jerzy W Jaromczyk Miros&#x;aw Kowaluk |
| |
| Institution: | a Department of Computer Science, University of Kentucky, Lexington, KY40506, USA;b Institute of Informatics, Warsaw University, Warsaw, Poland |
| |
| Abstract: | We provide lower and upper bounds for γ(n), the number of optimal solutions for the two-center problem: “Given a set S of n points in the real plane, find two closed discs whose union contains all of the points such that the radius of the larger disc is minimized.”The main result of the paper shows the matching upper and lower bounds for the two-center problem and demonstrates that γ(n)=n. |
| |
| Keywords: | Computational geometry Combinatorial geometry 2-center problem |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
