Common intersections of polygons

Laurence Boxer; Russ Miller

doi:10.1016/0020-0190(90)90193-2

Common intersections of polygons

Laurence Boxer
, Russ Miller

Department of Computer Science and Engineering

Niagara University

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

3 Scopus citations

Abstract

An algorithm is given for the detection of a common intersection with respect to a set of vertically convex planar polygons. A serial implementation is given, as well as parallel implementations for the CREW PRAM, hypercube, and mesh computers. Given an input of size n, the algorithm runs in θ(n log n) serial time and in θ(log n) time on a CREW PRAM, θ(log²n) time on a hypercube, and θ(n^{1 2}) time on a mesh, where all parallel machines are configured with n processors.

Original language	English
Pages (from-to)	249-254
Number of pages	6
Journal	Information Processing Letters
Volume	33
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(90)90193-2
State	Published - Jan 10 1990

Keywords

common intersection problem
Computational geometry
convex
parallel algorithms

Access to Document

10.1016/0020-0190(90)90193-2

Cite this

@article{22a58e7c8fc34023ab3df04f79a7d5a4,

title = "Common intersections of polygons",

abstract = "An algorithm is given for the detection of a common intersection with respect to a set of vertically convex planar polygons. A serial implementation is given, as well as parallel implementations for the CREW PRAM, hypercube, and mesh computers. Given an input of size n, the algorithm runs in θ(n log n) serial time and in θ(log n) time on a CREW PRAM, θ(log2n) time on a hypercube, and θ(n 1 2) time on a mesh, where all parallel machines are configured with n processors.",

keywords = "common intersection problem, Computational geometry, convex, parallel algorithms",

author = "Laurence Boxer and Russ Miller",

year = "1990",

month = jan,

day = "10",

doi = "10.1016/0020-0190(90)90193-2",

language = "English",

volume = "33",

pages = "249--254",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Common intersections of polygons

AU - Boxer, Laurence

AU - Miller, Russ

PY - 1990/1/10

Y1 - 1990/1/10

N2 - An algorithm is given for the detection of a common intersection with respect to a set of vertically convex planar polygons. A serial implementation is given, as well as parallel implementations for the CREW PRAM, hypercube, and mesh computers. Given an input of size n, the algorithm runs in θ(n log n) serial time and in θ(log n) time on a CREW PRAM, θ(log2n) time on a hypercube, and θ(n 1 2) time on a mesh, where all parallel machines are configured with n processors.

AB - An algorithm is given for the detection of a common intersection with respect to a set of vertically convex planar polygons. A serial implementation is given, as well as parallel implementations for the CREW PRAM, hypercube, and mesh computers. Given an input of size n, the algorithm runs in θ(n log n) serial time and in θ(log n) time on a CREW PRAM, θ(log2n) time on a hypercube, and θ(n 1 2) time on a mesh, where all parallel machines are configured with n processors.

KW - common intersection problem

KW - Computational geometry

KW - convex

KW - parallel algorithms

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

U2 - 10.1016/0020-0190(90)90193-2

DO - 10.1016/0020-0190(90)90193-2

M3 - Article

AN - SCOPUS:0025245341

SN - 0020-0190

VL - 33

SP - 249

EP - 254

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Common intersections of polygons

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this