On a triangle counting problem

Samir Khuller*, Joseph S B Mitchell

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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

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

Keywords

  • Range query
  • combinatorics
  • computational geometry

ASJC Scopus subject areas

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

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

Cite this