BASELINE BOUNDED HALF-PLANE VORONOI DIAGRAM

Given a set of points P = {p1, p2, . . . , pn} in the Euclidean plane, with each point piassociated with a given direction vi ϵ V . P(pi, vi) defines a half-plane and L(pi, vi)denotes the baseline that is perpendicular to vi and passing through pi. Define a regiondominated by pi and vi as a Baseline Bounded Half-Plane Voronoi Region, denoted asV or(pi, vi), if a point x ϵ V or(pi, vi), then (1) x ϵ P(pi, vi); (2) the line segment l(x, pi)does not cross any baseline; (3) if there is a point pj , such that x ϵ P(pj, vj ), and theline segment l(x, pj) does not cross any baseline then d(x, pi) ≤ d(x, pj), j ≠= i. TheBaseline Bounded Half-Plane Voronoi Diagram, denoted as V or(P, V ), is the union ofall V or(pi, vi). We show that V or(pi, vi) and V or(P, V ) can be computed in O(n log n)and O(n2 log n) time, respectively. For the heterogeneous point set, the same problem isalso considered.