Share Email Print

Proceedings Paper

Constant-time convex polygon algorithms on reconfigurable meshes
Author(s): Stephan Olariu; Jim L. Schwing; J. Zhang
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 9 April 1993
PDF: 11 pages
Proc. SPIE 1832, Vision Geometry, (9 April 1993); doi: 10.1117/12.142161
Show Author Affiliations
Stephan Olariu, Old Dominion Univ. (United States)
Jim L. Schwing, Old Dominion Univ. (United States)
J. Zhang, Elizabeth City State Univ. (United States)

Published in SPIE Proceedings Vol. 1832:
Vision Geometry
Robert A. Melter; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top