Counting Convex and Non-Convex 4-Holes in a Point Set

Young-Hun SUNG; Sang Won BAE

doi:10.1587/transfun.2020DMP0002

Counting Convex and Non-Convex 4-Holes in a Point Set

Young-Hun SUNG, Sang Won BAE

Full Text Views

0

Cite this

Summary :

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 Ω(n²) and O(n³) and the expected value of T is known to be Θ(n²) 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1094-1100

Publication Date: 2021/09/01

Publicized: 2021/03/18

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2020DMP0002

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category: Algorithms and Data Structures

Authors

Young-Hun SUNG
Kyonggi University
Sang Won BAE
Kyonggi University

Keyword

Erdös-Szekeres problem, counting algorithm, enumeration algorithm, polygon, discrete and computational geometry

Cite this

Copy

Young-Hun SUNG, Sang Won BAE, "Counting Convex and Non-Convex 4-Holes in a Point Set" in IEICE TRANSACTIONS on Fundamentals, vol. E104-A, no. 9, pp. 1094-1100, September 2021, doi: 10.1587/transfun.2020DMP0002.
Abstract: 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 Ω(n²) and O(n³) and the expected value of T is known to be Θ(n²) 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020DMP0002/_p

Copy

@ARTICLE{e104-a_9_1094,
author={Young-Hun SUNG, Sang Won BAE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Counting Convex and Non-Convex 4-Holes in a Point Set},
year={2021},
volume={E104-A},
number={9},
pages={1094-1100},
abstract={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 Ω(n²) and O(n³) and the expected value of T is known to be Θ(n²) 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.},
keywords={},
doi={10.1587/transfun.2020DMP0002},
ISSN={1745-1337},
month={September},}

Copy

TY - JOUR
TI - Counting Convex and Non-Convex 4-Holes in a Point Set
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1094
EP - 1100
AU - Young-Hun SUNG
AU - Sang Won BAE
PY - 2021
DO - 10.1587/transfun.2020DMP0002
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2021
AB - 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 Ω(n²) and O(n³) and the expected value of T is known to be Θ(n²) 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.
ER -