Constant-time convex polygon algorithms on reconfigurable meshes

Stephan Olariu; Jim L. Schwing; J. Zhang

doi:10.1117/12.142161

9 April 1993 Constant-time convex polygon algorithms on reconfigurable meshes

Stephan Olariu, Jim L. Schwing, J. Zhang

Proceedings Volume 1832, Vision Geometry; (1993) https://doi.org/10.1117/12.142161
Event: Applications in Optical Science and Engineering, 1992, Boston, MA, United States

Abstract

In an attempt to overcome the inefficiency of handling data transfer operations over long distances, mesh-connected computers have recently been augmented by the addition of various types of bus systems. One of the most efficient such augmented computer systems is referred to as the reconfigurable mesh, that is, a mesh-connected computer overlaid with a reconfigurable bus system. In this paper we propose constant-time algorithms on reconfigurable meshes for a number of important computational geometry tasks relevant to computer vision. These include testing an arbitrary polygon for convexity, computing the union and intersection of two convex polygons, testing whether two convex polygons are separable and, if so, constructing a separating line, solving the polygon containment problem for convex polygons, and others. Our solutions rely on a recently developed VLSI-optimal sorting algorithm for reconfigurable meshes and on a number of novel data movement techniques. The proposed algorithms translate immediately into constant-time algorithms that work on binary images.

Citation Download Citation

Stephan Olariu, Jim L. Schwing, and J. Zhang "Constant-time convex polygon algorithms on reconfigurable meshes", Proc. SPIE 1832, Vision Geometry, (9 April 1993); https://doi.org/10.1117/12.142161

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available