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
SN - 0020-0190
VL - 33
SP - 319
EP - 321
JO - Information Processing Letters
JF - Information Processing Letters
IS - 6
ER -