A new O( n·log n) algorithm for computing the intersection of convex polygons

We present a new O( n·log n) algorithm for computing the intersection of a set of arbitrary (possibly unbounded) polygons, where n is the total number of edges in the polygons. An interesting property of this algorithm is that if the intersection is empty, then the algorithm finds a minimal set of a...

Full description

Saved in:
Bibliographic Details
Published in:Pattern recognition 1987, Vol.20 (4), p.419-424
Main Author: Kundu, Sukhamay
Format: Article
Language:English
Subjects:
Algorithm
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Convex polygon
Exact sciences and technology
Pattern recognition. Digital image processing. Computational geometry
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a new O( n·log n) algorithm for computing the intersection of a set of arbitrary (possibly unbounded) polygons, where n is the total number of edges in the polygons. An interesting property of this algorithm is that if the intersection is empty, then the algorithm finds a minimal set of at most three polygons whose intersection is empty. The algorithm is based on a simple technique for detecting a redundant inequality among a set of inequalities of two variables.
ISSN:0031-3203
1873-5142
DOI:10.1016/0031-3203(87)90067-7