IEICE TRANSACTIONS on Fundamentals
Counting Convex and Non-Convex 4-Holes in a Point Set
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 Ω(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.
- 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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 Ω(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.
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 Ω(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.},
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 Ω(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.
ER -
English
