<p>An enclosing circle (by your definition) corresponds to a triangular face of the farthest point Delaunay triangulation, which is a triangulation of the convex hull of the input. For points in general position it always has exactly $h-2$ faces where $h$ is the number of convex hull vertices. Therefore the number of enclosing circles is also $h-2$.</p>

<p>They can be generated by constructing the farthest point Delaunay triangulation, in $O(n\log n)$ time.</p>

CC BY-SA 3.0
2013-02-19T00:34:27.917Z
2013-02-19T00:34:27.917Z
David Eppstein
<p>Several enclosing circles are possible for a given set of N 2D points. I am only talking about  enclosing circles having 3 or more points on the circumference. What is the asymptotic limit of the total number of distinct enclosing circles having 3 or more points on the circumference. The naive bound is $O(n^3)$ but tighter bound  should exist.</p>

<p>And also how to generate all such enclosing circles?</p>

<cg.comp-geom>
Number of distinct enclosing circles for N points
nomind
# Number of distinct enclosing circles for N points

(Asked by: username_0 on 2013-02-19)

Several enclosing circles are possible for a given set of N 2D points. I am only talking about enclosing circles having 3 or more points on the circumference. What is the asymptotic limit of the total number of distinct enclosing circles having 3 or more points on the circumference. The naive bound is $O(n^3)$ but tighter bound should exist.

And also how to generate all such enclosing circles?

**Tags:** cg.comp-geom


---

## 1 answers

### Answer by username_1 on 2013-02-19. Score: 9 | Accepted answer

An enclosing circle (by your definition) corresponds to a triangular face of the farthest point Delaunay triangulation, which is a triangulation of the convex hull of the input. For points in general position it always has exactly $h-2$ faces where $h$ is the number of convex hull vertices. Therefore the number of enclosing circles is also $h-2$.

They can be generated by constructing the farthest point Delaunay triangulation, in $O(n\log n)$ time.


---

