On the Area of Intersection between Two Closed 2-D Objects

Document Type

Article

Publication Date

1995

Publication Title

Information Sciences

Volume

82

Issue

1-2

First page number:

25

Last page number:

44

Abstract

The problem of extrema of the area of intersection between two 2-D closed objects is a subject of interest in industrial cloth manufacturing, toxic material storage in a work environment, large scale pesticide spraying in farms, and wildfire control in forests. The problem asks for the maximum and minimum of the area of intersection when a point on the boundary of one of the objects (axis point) rides on the boundary of the other with a fixed orientation to the edge on which it is riding (riding edge). The objects considered are: a convex polygon of size n and a circle, two convex polygons of sizes n and m, and two simple polygons of sizes n and m. An O(n2) time algorithm to locate the axis point on the boundary corresponding to the minimum of the area of intersection for the first case is presented. It is shown that for the case of the maximum area, the axis point can be located only using a numerical algorithm with a preset accuracy, except for some special cases. O(n(n + m)) time algorithms to locate the axis point corresponding to the extrema of the area of intersection of two convex polygons are presented. O(n2m) algorithms are established for the extrema of the area of intersection of two simple polygons.

Keywords

Algorithm complexity; Computational complexity; Computational geometry; Computer algorithms; Geometry; Intersection; Intersection theory; Polygonal shape; Polygons

Permissions

Use Find in Your Library, contact the author, or use interlibrary loan to garner a copy of the article. Publisher copyright policy allows author to archive post-print (author’s final manuscript). When post-print is available or publisher policy changes, the article will be deposited

UNLV article access

Search your library

Share

COinS