Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments

Details Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments

2011-07-26

arxiv.org/abs/1107.5204v1

Computer Science

Computational Geometry

17 pages, 4 figures, work presented in the paper is part of M. Kamarianakis' M.S. thesis

Scientific paper

In this paper we study the most-demanding predicate for computing the Euclidean Voronoi diagram of axes-aligned line segments, namely the Incircle predicate. Our contribution is two-fold: firstly, we describe, in algorithmic terms, how to compute the Incircle predicate for axes-aligned line segments, and secondly we compute its algebraic degree. Our primary aim is to minimize the algebraic degree, while, at the same time, taking into account the amount of operations needed to compute our predicate of interest. In our predicate analysis we show that the Incircle predicate can be answered by evaluating the signs of algebraic expressions of degree at most 6; this is half the algebraic degree we get when we evaluate the Incircle predicate using the current state-of-the-art approach. In the most demanding cases of our predicate evaluation, we reduce the problem of answering the Incircle predicate to the problem of computing the sign of the value of a linear polynomial (in one variable), when evaluated at a known specific root of a quadratic polynomial (again in one variable). Another important aspect of our approach is that, from a geometric point of view, we answer the most difficult case of the predicate via implicitly performing point locations on an appropriately defined subdivision of the place induced by the Voronoi circle implicated in the Incircle predicate.

Affiliated with

Also associated with

No associations

Rating

Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments 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 Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-93636