💻 computer science

A geometrical approach to determine the proximity of a point to an axisymmetric quadric in space

This paper introduces a novel geometrical method that classifies general quadrics as axisymmetric and efficiently computes the proximity of a point to such a surface by reducing the 3D problem to a categorized 2D conic analysis, demonstrating superior performance over commercial libraries like Bullet.

Original authors: Bibekananda Patra, Aditya Mahesh Kolte, Sandipan Bandyopadhyay

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bibekananda Patra, Aditya Mahesh Kolte, Sandipan Bandyopadhyay

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a robot navigating a room filled with strange, floating shapes: some are perfect spheres, others are squashed balls (like a rugby ball), some look like cooling towers (one-sheet hyperboloids), and others are like two funnels stuck together at their mouths (two-sheet hyperboloids). Your mission? To find the absolute shortest distance from your current spot to the nearest point on any of these shapes.

For a long time, mathematicians have tried to solve this "proximity problem" in 3D space. It's like trying to find the shortest path from a drone to a wobbly, 3D balloon without crashing. Usually, this involves solving massive, messy equations that take a computer a long time to crunch.

The Big Idea: Flatten the World
The authors of this paper, Bibekananda Patra, Aditya Mahesh Kolte, and Sandipan Bandyopadhyay, came up with a clever trick. They realized that if a shape is "axisymmetric" (meaning it looks the same if you spin it around a central stick, like a spinning top or a soda can), you don't need to look at the whole 3D world.

Instead, imagine slicing the 3D shape with a giant, invisible knife. This knife is a flat plane that passes through the shape's central spinning stick and your robot's position. When you cut the shape this way, the 3D object turns into a simple 2D curve on that flat slice—like turning a 3D apple into a 2D circle or an oval on a piece of paper.

The paper proves that finding the shortest distance in the complex 3D world is exactly the same as finding the shortest distance on this simple 2D slice. It's like realizing you don't need to climb a mountain to measure its height; you just need to look at its shadow on the ground.

The New Map: Sorting the Shapes
Before you can slice the shape, you have to know what kind of shape you're dealing with. The paper introduces a new "flowchart" (a decision tree) to sort any weird 3D shape into one of seven specific types of axisymmetric shapes:

Spheroids (squashed or stretched spheres)
Hyperboloids (cooling tower shapes or double funnels)
Cones (ice cream cones)
Paraboloids (satellite dishes)
Cylinders (pipes)
Spheres (perfect balls)

The authors explicitly state that while people have figured out how to measure distances to ellipsoids (squashed spheres) before, no one had created a complete, geometric guide for all these other axisymmetric shapes until now. They also argue against the old way of solving this, which often relied on heavy numerical guessing or complex 3D projections. Instead, they use pure geometry—looking at things like the "sub-normal" (a specific line related to the curve's slope) and the "eccentricity" (how stretched out the shape is).

The Slice-and-Dice Method
Once the shape is identified, the math gets fun. The authors break the problem down based on where your point (the robot) is standing relative to the 2D curve:

If you are on the center line: The math is simple.
If you are off to the side: The math gets trickier, turning into a "cubic equation" (a puzzle with three possible answers) for parabolas or a "quartic equation" (a puzzle with four possible answers) for ellipses and hyperbolas.

The paper doesn't just say "solve the equation." It carefully categorizes every possible scenario. For example, if you are inside a parabola, the answer is different than if you are outside. If you are on the axis of symmetry, the answer is different again. They even handle the "weird" cases where the point lies exactly on the center line, which previous methods often struggled with or approximated.

The Results: Fast and Furious
The authors didn't just draw pictures; they coded this method in the C programming language and tested it on a powerful computer (an AMD Ryzen 9 7950x).

Here is the proof of how fast it is:

For a Sphere, the calculation takes 0 nanoseconds (it's so simple it's instant).
For a Cone, it takes 8 nanoseconds.
For a Cylinder, 21 nanoseconds.
Even for the most complex shapes like a Hyperboloid of one sheet, it takes only 88 nanoseconds.

To put this in perspective, they compared their method to a famous commercial software library called Bullet (often used in video games and robotics). They found that the Bullet library was 19 times slower for the cone and a whopping 106 times slower for the sphere compared to their new geometric method.

What This Means (and What It Doesn't)
The paper concludes that this geometric approach is a "novel" (new) way to solve the problem. It is proved to be faster than the commercial library in these specific tests. The authors suggest this could be very useful for designing robots and avoiding collisions, where speed is everything.

However, the paper is careful not to claim this solves every distance problem in the universe. It specifically focuses on axisymmetric shapes (those with a central spinning axis). It does not claim to solve the distance problem for a random, lumpy potato-shaped object that doesn't spin symmetrically.

In short, the authors have handed us a new, super-fast flashlight that lets us see the shortest path to a spinning 3D shape by simply looking at its 2D shadow, and they've shown that this flashlight is significantly brighter and faster than the ones we were using before.

Technical Summary: A Geometrical Approach to Determine the Proximity of a Point to an Axisymmetric Quadric in Space

Problem Statement
The paper addresses the problem of computing the shortest distance (proximity) between a given point $p_0$ in $\mathbb{R}^3$ and a general quadratic surface (quadric) that does not contain the point. While the proximity of a point to specific quadrics like ellipsoids and hyperboloids has been studied, the authors note a lack of literature regarding the systematic identification of axisymmetric quadrics (AQs) and the computation of proximity for the full range of AQs (including spheroids, paraboloids, cylinders, cones, and spheres). Existing methods often rely on numerical optimization or closed-form derivations that result in high-degree polynomial equations, which can be computationally expensive.

Methodology
The proposed approach utilizes a geometric reduction strategy to transform the 3D problem into a 2D problem, leveraging the symmetry of the surfaces.

Identification of Axisymmetric Quadrics (AQs):
The authors first present a classification method to distinguish AQs from general non-axisymmetric quadrics. This is achieved by analyzing the coefficients of the general quadric equation $S(x) = 0$ . The method relies on:
- The discriminant ( $\Delta$ ) of the characteristic polynomial of the upper-left $3\times3$ sub-matrix $B$ . If $\Delta = 0$ , the quadric is axisymmetric.
- The determinant of the full $4\times4$ matrix $A$ ( $\det(A)$ ) and the invariant $J_3$ to further classify the AQ into central (e.g., spheroids, hyperboloids, cones, spheres) or non-central (e.g., paraboloids, cylinders) types.
- This classification is visualized via a flowchart (Fig. 4) and avoids rank computations in favor of invariant-based checks for efficiency.
Reduction from $\mathbb{R}^3$ to $\mathbb{R}^2$ :
Once an AQ is identified, the authors define a plane $P$ that contains the axis of symmetry ( $v_3$ ) of the quadric and the given point $p_0$ . The intersection of this plane with the quadric results in a conic section (ellipse, hyperbola, parabola, circle, or pairs of lines). The problem of finding the shortest distance from $p_0$ to the 3D surface is thus reduced to finding the normal distance from the projected point $p_p$ to this 2D conic.
Geometric Solution in $\mathbb{R}^2$ :
The core novelty lies in solving the 2D proximity problem using the geometric properties of conics (sub-normal, semi-major/minor axes, eccentricity, and slope) rather than standard algebraic projection methods.
- Parabola: The problem is categorized based on whether $p_p$ lies on the axis of symmetry. If not, the solution involves solving a cubic equation derived from the sub-normal property. Special closed-form expressions are provided for cases where $p_p$ lies on the axis.
- Ellipse and Hyperbola: Similarly, the problem is categorized based on whether $p_p$ lies on the major or minor axes. For general positions, the method derives a quartic equation. The authors provide detailed sub-cases for the real roots of these equations (e.g., four distinct roots, repeated roots) to ensure accurate distance calculation in all geometric configurations.
- Other AQs: For spheres, cones, and cylinders, the proximity is computed using simpler geometric projections (e.g., distance to a circle or perpendicular distance to parallel lines).

Key Contributions

Systematic Classification: A novel flowchart-based method to identify and classify any general quadric as an axisymmetric quadric using invariants ( $\Delta, J_3, \det(A)$ ) rather than matrix ranks.
Dimensionality Reduction: A rigorous reduction of the 3D proximity problem to a 2D problem by utilizing the symmetry axis, a reduction not explicitly detailed in the cited literature for general AQs.
Novel 2D Sub-cases: The categorization of the 2D proximity problem into specific sub-cases based on the point's location relative to the conic's axes. This includes handling special cases (e.g., points on the major axis of an ellipse) where standard quartic/cubic derivations might fail or become invalid, providing closed-form solutions for these scenarios.
Geometric Derivation: The derivation of the governing polynomial equations (cubic for parabolas, quartic for ellipses/hyperbolas) using geometric properties like the sub-normal, which the authors argue is more computationally efficient than standard orthogonal projection methods.

Results
The method was implemented in the C programming language and tested on a single thread of an AMD Ryzen 9 7950x processor.

Execution Time: The total time to identify an AQ and compute the proximity for all tested cases (spheroids, hyperboloids, paraboloids, cylinders, cones, spheres) was found to be under 90 nanoseconds on average.
Comparison: The proposed method was compared against the commercial Bullet physics library (modified for these specific tasks). The results indicated that the proposed geometric method is approximately 19 times faster for cone proximity and 106 times faster for sphere proximity compared to the Bullet library.
Validation: Numerical examples for all seven types of AQs were provided, with results visualized as spheres centered at $p_0$ tangent to the respective surfaces, confirming the geometric validity of the computed distances.

Significance and Claims
The authors claim that their approach offers a highly efficient, geometrically intuitive solution to a problem that is often treated via complex numerical optimization or heavy algebraic manipulation. By reducing the problem to $\mathbb{R}^2$ and utilizing specific geometric properties, the size of the symbolic expressions required is significantly smaller (kilobytes vs. megabytes in some algebraic software contexts), leading to faster execution. The paper asserts that this method is particularly suitable for real-time applications in robotics, computer graphics, and collision avoidance where computational speed and accuracy are critical. The authors explicitly state that the classification of the 2D problem into the specific sub-cases presented is a novel contribution not found in existing literature.

More like this