Name
Abstract | ||
|---|---|---|
The triangle-perimeter 2-site distance function defines the “distance” from a point x to two other points p,q as the perimeter of the triangle whose vertices are x,p,q. Accordingly, given a set S of n points in the plane, the Voronoi diagram of S with respect to the triangle-perimeter distance, is the subdivision of the plane into regions, where the region of the pair
p,q ∈ S is the locus of all points closer to p,q (according to the triangle-perimeter distance) than to any other pair of sites in S. In this paper we prove a theorem about the perimeters of triangles, two of whose vertices are on a given circle. We use
this theorem to show that the combinatorial complexity of the triangle-perimeter 2-site Voronoi diagram is O(n
2 + ε
) (for any ε> 0). Consequently, we show that one can compute the diagram in O(n
2 + ε
) time and space.
|
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-16007-3_3 | Transactions on computational science IX |
Keywords | DocType | Volume |
triangle-perimeter distance,points p,2-site distance function,combinatorial complexity,n point,pair p,triangle-perimeter two-site voronoi diagram,site voronoi diagram,triangleperimeter distance,voronoi diagram,planar map,distance function | Journal | 9 |
ISSN | ISBN | Citations |
0302-9743 | 3-642-16006-9 | 5 |
PageRank | References | Authors |
0.50 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Iddo Hanniel | 1 | 197 | 12.98 |
| Gill Barequet | 2 | 809 | 86.97 |