Circle separability queries in logarithmic time

Details Circle separability queries in logarithmic time Circle separability queries in logarithmic time

2012-03-28

arxiv.org/abs/1203.6266v1

Computer Science

Computational Geometry

Scientific paper

Let $P$ be a set of $n$ points in the plane. In this paper we study a new variant of the circular separability problem in which a point set $P$ is preprocessed so that one can quickly answer queries of the following form: Given a geometric object $Q$, report the minimum circle containing $P$ and exluding $Q$. Our data structure can be constructed in $O(n\log n)$ time using O(n) space, and can be used to answer the query when $Q$ is either a circle or a convex $m$-gon in $O(\log n)$ or $O(\log n + \log m)$ time, respectively.

Affiliated with

Also associated with

No associations

Rating

Circle separability queries in logarithmic time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Circle separability queries in logarithmic time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circle separability queries in logarithmic time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-272790