Geometric algorithms for finding a point in the intersection of balls
Do \(n\) balls in Euclidean \(m\)-space given by their centres and radii intersect? If so determine an intersection point. This task may be accomplished (after \(0(n^2)\) preprocessing) in 2-space in \(O(n^3)\) time by a naive method which checks intersection points of pairs of boundary circles, and in \(O(n^2\log n)\) time by a more involved method checking this intersection along the boundary circle of (possibly) each ball. In higher dimensions, the task may similarly be reduced to dimension \(m-1\), yielding a recursive method of \(O(n^{2m-4}(nm^2+m^3+n^2\log n))\).
- On intersecting a point set with Euclidean balls
- ALGORITHMS FOR BALL HULLS AND BALL INTERSECTIONS IN NORMED PLANES
- Intersection algorithms for lines and circles
- Publication:4934236
- An algorithm for finding intersection between ball B-spline curves
- scientific article; zbMATH DE number 480245
- Intersections of balls and the ball hull mapping
- An optimal algorithm for intersecting line segments in the plane
- Computing the convex hull of line intersections
- Efficient dynamic algorithms for some geometric intersection problems
- scientific article; zbMATH DE number 193847 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- Linear Matrix Inequalities in System and Control Theory
- On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
- Hitting or avoiding balls in Euclidean space
- Is a finite intersection of balls covered by a finite union of balls in Euclidean spaces?
- Projection of a point onto the intersection of spheres in linear varieties
- Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
- Reliable computation of the points of intersection of \(n\) spheres in \({\mathbb{R}}^n\)
- Inflating balls is NP-hard
- ALGORITHMS FOR BALL HULLS AND BALL INTERSECTIONS IN NORMED PLANES
- scientific article; zbMATH DE number 124000 (Why is no real title available?)
- A note on computing the intersection of spheres in \(\mathbb{R}^n\)
- On intersecting a point set with Euclidean balls
This page was built for publication: Geometric algorithms for finding a point in the intersection of balls
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827997)
