On a triangle counting problem

Samir Khuller*, Joseph S B Mitchell

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)319-321
Number of pages3
JournalInformation Processing Letters
Issue number6
StatePublished - Feb 10 1990


  • Range query
  • combinatorics
  • computational geometry

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'On a triangle counting problem'. Together they form a unique fingerprint.

Cite this