Name
Abstract | ||
|---|---|---|
Given a set of points P = {p(1), p(2), . . . , p(n)} in the Euclidean plane, with each point p(i) associated with a given direction v(i) is an element of V. P(p(i), v(i)) defines a half-plane and L(p(i), v(i)) denotes the baseline that is perpendicular to v(i) and passing through p(i). Define a region dominated by p(i) and v(i) as a Baseline Bounded Half-Plane Voronoi Region, denoted as V or(p(i), v(i)), if a point x is an element of V or(p(i), v(i)), then (1) x is an element of P(p(i), v(i)); (2) the line segment l(x, p(i)) does not cross any baseline; (3) if there is a point p(j), such that x is an element of P(p(j), v(j)), and the line segment l(x, p(j)) does not cross any baseline then d(x, p(i)) <= d(x, p(j)), j not equal i. The Baseline Bounded Half-Plane Voronoi Diagram, denoted as V or(P, V), is the union of all V or(p(i), v(i)). We show that V or(p(i), v(i)) and V or(P, V) can be computed in O(n log n) and O(n(2) log n) time, respectively. For the heterogeneous point set, the same problem is also considered. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1142/S1793830913500213 | DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS |
Keywords | Field | DocType |
Half-plane, baseline, Voronoi diagram | Pi,Discrete mathematics,Line segment,Perpendicular,Combinatorics,Voronoi diagram,Euclidean geometry,Point set,Time complexity,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
5 | 3 | 1793-8309 |
Citations | PageRank | References |
1 | 0.35 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bing Su | 1 | 17 | 4.72 |
| Yinfeng Xu | 2 | 1636 | 108.18 |
| Binhai Zhu | 3 | 903 | 109.96 |