TY - GEN
T1 - Overlap detection using minkowski sum in two-dimensional layout
AU - Yu, Chan
AU - Manodchehri, Souran
N1 - Publisher Copyright:
Copyright © 1999 by ASME.
PY - 1999
Y1 - 1999
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=1842764086&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=1842764086&partnerID=8YFLogxK
U2 - 10.1115/DETC99/DAC-8570
DO - 10.1115/DETC99/DAC-8570
M3 - Conference contribution
AN - SCOPUS:1842764086
T3 - Proceedings of the ASME Design Engineering Technical Conference
SP - 763
EP - 770
BT - 25th Design Automation Conference
T2 - ASME 1999 Design Engineering Technical Conferences, DETC 1999
Y2 - 12 September 1999 through 16 September 1999
ER -