Ex - Disk and Segments Editorial by en_translator
We can consider that this problem asks to find \[\min _ {(x,y)\in\mathbb R ^ 2}f(x,y),\] where \(f(x,y)\coloneqq\) the minimum radius of a closed disk centered at point \((x,y)\) that shares a point with all the segments.
Important fact: \(f(x,y)\) is convex.
Proof
Lemma 1
For \(p\in\mathbb R^2\), let \(d _ p(x,y)\) be the distance between point \(p\) and point \((x,y)\). Then \(d _ p\colon\mathbb R ^ 2\to\mathbb R _ {{}\geq0}\) is convex.
Proof of lemma 1
The epigraph \(\left\lbrace(x,y,z)\mid z\geq d _ p(x,y)\right\rbrace\) forms a cone, which is convex. Thus, \(d _ p(x,y)\) is convex.
Lemma 2
For a segment \(s\) connecting \(a,b\in\mathbb R^2\), let \(d _ s(x,y)\) be the distance between segment \(s\) and point \((x, y)\); then \(d _ s\colon\mathbb R^2\to\mathbb R _ {{}\geq0}\) is convex.
Proof of lemma 2
We show that \(d _ s((1-t)c+td)\leq(1-t)d _ s(c )+td _ s(d)\) for all \(c,d\in\mathbb R^2\) and \(0\leq t\leq1\).
There exist points \(p _ c\) and \(p _ d\) on \(s\) such that \(d _ s(c )=d _ {p _ c}(c )\) and \(d _ s(d)=d _ {p _ d}(d)\). Taking \(p=(1-t)p _ c+tp _ d\), we have \(d _ s((1-t)c+td)\leq d _ p((1-t)c+td)\) by definition of \(d _ s\).
Noting \(d _ q(r )=d _ O(r-q)\) for all \(q,r\in\mathbb R^2\), where \(O=(0,0)\) is the origin, we see that \[d _ p((1-t)c+td)=d _ O((1-t)(c-p _ c)+t(d-p _ d))\] and \[d _ {p _ c}(c )=d _ O(c-p _ c),d _ {p _ d}(d)=d _ O(d-p _ d).\] By lemma 1, \(d _ O((1-t)(c-p _ c)+t(d-p _ d))\leq(1-t)d _ O(c-p _ c)+td _ O(d-p _ d)\); so \[d _ s((1-t)c+td)\leq d _ p((1-t)c+td)\leq(1-t)d _ s(c )+td _ s(d),\] which is what we wanted.
Lemma 3
If functions \(g _ i\colon\mathbb R ^ 2\to\mathbb R\ (i=1,2,\ldots,n)\) are convex, so is \(\displaystyle g(x,y)\coloneqq\max _ ig _ i(x,y)\).
Proof of lemma 3
We show that \(g((1-t)a+tb)\leq(1-t)g(a)+tg(b)\) for all \(a,b\in\mathbb R^2\) and \(0\leq t\leq1\).
By definition of \(g\), there exists \(i\) such that \(g((1-t)a+tb)=g _ i((1-t)a+tb)\). Since \(g _ i\) is concave, \(g _ i((1-t)a+tb)\leq(1-t)g _ i(a)+tg _ i(b)\). By definition of \(g\), we have \({} ^ \forall i.\;g\geq g _ i\); hence, \((1-t)g _ i(a)+tg _ i(b)\leq(1-t)g(a)+tg(b)\) is proven.
For the given segments \(s _ 1,s _ 2,\ldots,s _ N\), we have \[f(x,y)=\max _ {i=1,2,\ldots,N}d _ {s _ i}(x,y)\].
Since each \(d _ {s _ i}\) is convex by lemma 2, \(f(x,y)\) is also convex by lemma 3.
When a convex (or unimodal) function of one variable is known to take the minimum value within a specific range, we can approximate the minimum value with a trinary search.
Consider the following function: \[F(x):=\min _ {y\in\mathbb R}f(x,y).\] then we can show that \(F(x)\) is a convex function of one variable.
Proof
We will show that the epigraph \(\left\lbrace(x,z)\mid z\geq F(x)\right\rbrace\) of \(F\) is convex. For any two points \(a\) and \(b\) in the epigraph of \(F\), there exist points \(a ^ \prime\) and \(b ^ \prime\) inside the epigraph \(\left\lbrace(x,y,z)\mid z\geq f(x,y)\right\rbrace\) of \(f\).
By the convexity of \(f\), the segment connecting \(a ^ \prime,b ^ \prime\) is contained in the epigraph of \(f\); that is, all points \((x,y,z)\) on the segment satisfy \(z\geq f(x,y)\). By definition of \(F\), we have \(F(x)\leq f(x,y)\), so \(z\geq F(x)\); thus, the segment connecting \(a\) and \(b\) is contained in the epigraph of \(F\).
Obviously, \(f(x,y)\) for a fixed \(x\) is a convex function, so the problem has been solved by performing trinary search within trinary search.
The following is a sample code.
#include <iostream>
#include <tuple>
#include <vector>
#include <cmath>
#include <ranges>
int main() {
using namespace std;
unsigned N;
cin >> N;
using real = double;
using segment_type = tuple<real, real, real, real>;
using point_type = tuple<real, real>;
vector<segment_type> segments(N);
for (auto&&[a, b, c, d] : segments)
cin >> a >> b >> c >> d;
// Distance of two points
const auto distance_point_and_point{[](const point_type &point0, const point_type &point1) {
const auto&[x, y]{point0};
const auto&[z, w]{point1};
return hypot(x - z, y - w);
}};
// Distance of point and segment
const auto distance_segment_and_point{[&](const segment_type &segment, const point_type &point) {
const auto&[a, b, c, d]{segment};
const auto&[x, y]{point};
if ((a - c) * (a - x) + (b - d) * (b - y) < 0)
return distance_point_and_point({a, b}, {x, y});
if ((c - a) * (c - x) + (d - b) * (d - y) < 0)
return distance_point_and_point({c, d}, {x, y});
return abs((a - c) * (b - y) - (b - d) * (a - x)) / distance_point_and_point({a, b}, {c, d});
}};
// minimum radius of a closed circle centered at the given point that shares a point with all segments
const auto minimum_crossing_circle{[&](const point_type &point) {
real ret{};
for(const auto& segment : segments)
ret = max(ret, distance_segment_and_point(segment, point));
return ret;
}};
// Use trinary search to find the minimum value of a unimodal function
const auto minimize_unimodal_function{[](real L, real R, auto &&function) {
for (const auto _ : ranges::views::iota(0, 100)) {
auto M1{(L * 2 + R) / 3};
auto M2{(L + 2 * R) / 3};
if (function(M1) < function(M2))
R = M2;
else
L = M1;
}
return function(L);
}};
cout << minimize_unimodal_function(0, 1000, [&](auto x) {
// Find the minimum value of f(x, y) for a fixed x
return minimize_unimodal_function(0, 1000, [&](auto y) {
// Given x and y, we can find the minimum radius
return minimum_crossing_circle({x, y});
});
}) << endl;
return 0;
}
One can also use scipy.optimize.minimize to find the minimum value of \(f(x,y)\).
from scipy.optimize import minimize
from math import sqrt
N = int(input())
segments = [tuple(map(int, input().split())) for i in range(N)]
def f(param):
x, y = param
ret = 0
for a, b, c, d in segments:
if (a - c) * (a - x) + (b - d) * (b - y) < 0:
ret = max(ret, sqrt((a - x) ** 2 + (b - y) ** 2))
elif (c - a) * (c - x) + (d - b) * (d - y) < 0:
ret = max(ret, sqrt((c - x) ** 2 + (d - y) ** 2))
else:
ret = max(ret, abs((a - c) * (b - y) - (b - d) * (a - x)) / sqrt((a - c) ** 2 + (b - d) ** 2))
return ret
print(minimize(f, (500, 500), args=(), method='Nelder-Mead').fun)
posted:
last update: