Overlap detection using minkowski sum in two-dimensional layout

Chan Yu, Souran Manodchehri

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

In optimal layout problems, which are often demanded by many industries, it is desired to have new computer-based approaches that are fast and effective. To determine the overall speed of layout procedure, one has to consider not only the search algorithm but also the performance of overlap detection algorithm. In this paper, a new methodology of detecting an overlap in two-dimensional layout problem is presented. This method introduces the concept of Minkowski sum, which is defined as an algebraic sum of two point sets, to the overlap detection. Using mathematical relations, the algorithm can rapidly detect if two convex objects.are overlapping, fully contained or separated. Fast detection of overlaps eventually allows user to accelerate the overall speed of layout algorithms. In addition, to obtain the robustness of this method it is being extended to the cases involving irregular-shaped non-convex objects.

Original languageEnglish
Title of host publication25th Design Automation Conference
Pages763-770
Number of pages8
ISBN (Electronic)9780791819715
DOIs
StatePublished - 1999
EventASME 1999 Design Engineering Technical Conferences, DETC 1999 - Las Vegas, United States
Duration: 12 Sep 199916 Sep 1999

Publication series

NameProceedings of the ASME Design Engineering Technical Conference
Volume1

Conference

ConferenceASME 1999 Design Engineering Technical Conferences, DETC 1999
Country/TerritoryUnited States
CityLas Vegas
Period12/09/9916/09/99

Fingerprint

Dive into the research topics of 'Overlap detection using minkowski sum in two-dimensional layout'. Together they form a unique fingerprint.

Cite this