Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 9 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.