The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] discrete and computational geometry(1hit)

1-1hit
  • Counting Convex and Non-Convex 4-Holes in a Point Set

    Young-Hun SUNG  Sang Won BAE  

     
    PAPER-Algorithms and Data Structures

      Pubricized:
    2021/03/18
      Vol:
    E104-A No:9
      Page(s):
    1094-1100

    In this paper, we present an algorithm that counts the number of empty quadrilaterals whose corners are chosen from a given set S of n points in general position. Our algorithm can separately count the number of convex or non-convex empty quadrilaterals in O(T) time, where T denotes the number of empty triangles in S. Note that T varies from Ω(n2) and O(n3) and the expected value of T is known to be Θ(n2) when the n points in S are chosen uniformly and independently at random from a convex and bounded body in the plane. We also show how to enumerate all convex and/or non-convex empty quadrilaterals in S in time proportional to the number of reported quadrilaterals, after O(T)-time preprocessing.