Counting convex polygons in planar point sets

Joseph S.B. Mitchell; Günter Rote; Gopalakrishnan Sundaram; Gerhard Woeginger

doi:10.1016/0020-0190(95)00130-5

Counting convex polygons in planar point sets

Joseph S.B. Mitchell
, Günter Rote
, Gopalakrishnan Sundaram
, Gerhard Woeginger

Applied Mathematics and Statistics

Graz University of Technology
Esri

Research output: Contribution to journal › Article › peer-review

22 Scopus citations

Abstract

Given a set S of n points in the plane, we compute in time O(n³) the total number of convex polygons whose vertices are a subset of S. We give an O(m · n³) algorithm for computing the number of convex k-gons with vertices in S, for all values k = 3,..., m; previously known bounds were exponential (O(n^{{top left corner} k 2{top right corner}}). We also compute the number of empty convex polygons (resp.,k-gons, k ≤ m) with vertices in S in time O(n³) (resp., O(m · n³)).

Original language	English
Pages (from-to)	45-49
Number of pages	5
Journal	Information Processing Letters
Volume	56
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(95)00130-5
State	Published - Oct 13 1995

Keywords

Combinatorics
Computational geometry
Convexity
Dynamic programming Partially

Access to Document

10.1016/0020-0190(95)00130-5

Cite this

@article{a702520fb9e6464fa45b10f3847779a5,

title = "Counting convex polygons in planar point sets",

abstract = "Given a set S of n points in the plane, we compute in time O(n3) the total number of convex polygons whose vertices are a subset of S. We give an O(m · n3) algorithm for computing the number of convex k-gons with vertices in S, for all values k = 3,..., m; previously known bounds were exponential (O(n\{top left corner\} k 2\{top right corner\}). We also compute the number of empty convex polygons (resp.,k-gons, k ≤ m) with vertices in S in time O(n3) (resp., O(m · n3)).",

keywords = "Combinatorics, Computational geometry, Convexity, Dynamic programming Partially",

author = "Mitchell, \{Joseph S.B.\} and G{\"u}nter Rote and Gopalakrishnan Sundaram and Gerhard Woeginger",

year = "1995",

month = oct,

day = "13",

doi = "10.1016/0020-0190(95)00130-5",

language = "English",

volume = "56",

pages = "45--49",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "1",

}

TY - JOUR

T1 - Counting convex polygons in planar point sets

AU - Mitchell, Joseph S.B.

AU - Rote, Günter

AU - Sundaram, Gopalakrishnan

AU - Woeginger, Gerhard

PY - 1995/10/13

Y1 - 1995/10/13

N2 - Given a set S of n points in the plane, we compute in time O(n3) the total number of convex polygons whose vertices are a subset of S. We give an O(m · n3) algorithm for computing the number of convex k-gons with vertices in S, for all values k = 3,..., m; previously known bounds were exponential (O(n{top left corner} k 2{top right corner}). We also compute the number of empty convex polygons (resp.,k-gons, k ≤ m) with vertices in S in time O(n3) (resp., O(m · n3)).

AB - Given a set S of n points in the plane, we compute in time O(n3) the total number of convex polygons whose vertices are a subset of S. We give an O(m · n3) algorithm for computing the number of convex k-gons with vertices in S, for all values k = 3,..., m; previously known bounds were exponential (O(n{top left corner} k 2{top right corner}). We also compute the number of empty convex polygons (resp.,k-gons, k ≤ m) with vertices in S in time O(n3) (resp., O(m · n3)).

KW - Combinatorics

KW - Computational geometry

KW - Convexity

KW - Dynamic programming Partially

UR - https://www.scopus.com/pages/publications/28144435840

U2 - 10.1016/0020-0190(95)00130-5

DO - 10.1016/0020-0190(95)00130-5

M3 - Article

AN - SCOPUS:28144435840

SN - 0020-0190

VL - 56

SP - 45

EP - 49

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Counting convex polygons in planar point sets

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this