TY - JOUR

T1 - On a triangle counting problem

AU - Khuller, Samir

AU - Mitchell, Joseph S B

N1 - Funding Information:
* Supported by NSF Grant DCR 85-52938 and PYI match-ing funds from AT&T Bell Labs. and Suu Microsystems. ** Partially supported by NSF Grants I 8853642 and a grant from I-Iughes Research Labs.

PY - 1990/2/10

Y1 - 1990/2/10

N2 - We consider the following problem: given a set S of n points in the plane, we would like to compute for each point pε{lunate}S, how many triangles with corners at points in set S contain p. We give an O(n2) algorithm to solve the problem.

AB - We consider the following problem: given a set S of n points in the plane, we would like to compute for each point pε{lunate}S, how many triangles with corners at points in set S contain p. We give an O(n2) algorithm to solve the problem.

KW - Range query

KW - combinatorics

KW - computational geometry

UR - http://www.scopus.com/inward/record.url?scp=0025386369&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025386369&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(90)90217-L

DO - 10.1016/0020-0190(90)90217-L

M3 - Article

AN - SCOPUS:0025386369

VL - 33

SP - 319

EP - 321

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 6

ER -