On a triangle counting problem

Samir Khuller; Joseph S.B. Mitchell

doi:10.1016/0020-0190(90)90217-L

On a triangle counting problem

Samir Khuller
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Cornell University

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

Abstract

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(n²) algorithm to solve the problem.

Original language	English
Pages (from-to)	319-321
Number of pages	3
Journal	Information Processing Letters
Volume	33
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(90)90217-L
State	Published - Feb 10 1990

Keywords

combinatorics
computational geometry
Range query

Access to Document

10.1016/0020-0190(90)90217-L

Cite this

@article{efd79191c3574db1987d351469d913fa,

title = "On a triangle counting problem",

abstract = "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.",

keywords = "combinatorics, computational geometry, Range query",

author = "Samir Khuller and Mitchell, \{Joseph S.B.\}",

year = "1990",

month = feb,

day = "10",

doi = "10.1016/0020-0190(90)90217-L",

language = "English",

volume = "33",

pages = "319--321",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "6",

}

TY - JOUR

T1 - On a triangle counting problem

AU - Khuller, Samir

AU - Mitchell, Joseph S.B.

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 - combinatorics

KW - computational geometry

KW - Range query

UR - https://www.scopus.com/pages/publications/0025386369

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 -

On a triangle counting problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this