TY - JOUR

T1 - Empty pseudo-triangles in point sets

AU - Ahn, H.K.

AU - Bae, S.W.

AU - Kreveld, van, M.J.

AU - Reinbacher, I.

AU - Speckmann, B.

PY - 2011

Y1 - 2011

N2 - We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between T(n2) and T(n3) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between T(n3) and T(n6). If we count only star-shaped pseudo-triangles, the bounds are T(n2) and T(n5). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n3) time. In the general case, the running times are O(n6) for the maximization problems and O(nlogn) for the minimization problems.

AB - We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between T(n2) and T(n3) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between T(n3) and T(n6). If we count only star-shaped pseudo-triangles, the bounds are T(n2) and T(n5). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n3) time. In the general case, the running times are O(n6) for the maximization problems and O(nlogn) for the minimization problems.

U2 - 10.1016/j.dam.2011.07.026

DO - 10.1016/j.dam.2011.07.026

M3 - Article

SN - 0166-218X

VL - 159

SP - 2205

EP - 2213

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 18

ER -