检索结果-内蒙古大学图书馆

time-optimal VISIBILITY-RELATED algorithms ON MESHES WITH MULTIPLE BROADCASTING

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第7期6卷 687-703页

作者： BHAGAVATHI, D BOKKA, VV GURLA, H OLARIU, S SCHWING, JL STOJMENOVIC, I ZHANG, JY OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 UNIV OTTAWA DEPT COMP SCIOTTAWAON K1N 9B4CANADA ELIZABETH CITY STATE UNIV DEPT MATH & COMP SCIELIZABETH CITYNC 27909

Given a collection of objects in the plane along with a viewpoint omega, the visibility problem involves determining the portion of each object that is visible to an observer positioned at omega. The visibility problem is central to various application areas including computer graphics, image processing, VLSI design, and robot navigation, among many others. The main contribution of this work is to provide time-optimal solutions to this problem for several classes of objects, namely ordered line segments, disks, and iso-oriented rectangles in the plane. In addition, our visibility algorithm for line segments is at the heart of time-optimal solutions for determining, for each element in a given sequence of real numbers, the position of the nearest larger element within that sequence, triangulating a set of points in the plane, determining the visibility pairs among a set of vertical line segments, and constructing the dominance and visibility graphs of a set of iso-oriented rectangles in the plane. All the algorithms in this paper involve an input of size n and run in O(log n) time on a mesh with multiple broadcasting of size n x n. This is the first instance of time-optimal solutions for these problems on this architecture.

关键词： VISIBILITY TRIANGULATION COMPACTION DOMINANCE GRAPH VISIBILITY GRAPH ROBOTICS IMAGE PROCESSING COMPUTER GRAPHICS VLSI DESIGN COMPUTATIONAL GEOMETRY MESHES WITH MULTIPLE BROADCASTING PARALLEL algorithms time-optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

time- and cost-optimal parallel algorithms for the dominance and visibility graphs

引用

VLSI DESIGN 1996年第1期4卷 33-40页

作者： Bhagavathi, D Gurla, H Olariu, S Schwing, JL Zhang, J OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 ELIZABETH CITY STATE UNIV DEPT MATH & COMP SCIELIZABETH CITYNC 27909

The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in theta(log n) time using n processors in the CREW model.

关键词： CAD compaction constraint graph dominance graph visibility graph parallel algorithms lower bounds time-optimal algorithms CREW

来源：评论

学校读者我要写书评

暂无评论

time-optimal DIGITAL GEOMETRY algorithms ON MESHES WITH MULTIPLE BROADCASTING

引用

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE 1995年第4期9卷 601-613页

作者： BOKKA, V GURLA, H OLARIU, S SCHWING, JL STOJMENOVIC, I OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 UNIV OTTAWA DEPT COMP SCIOTTAWAONCANADA

The main contribution of this work is to show that a number of digital geometry problems can be solved elegantly on meshes with multiple broadcasting by using a time-optimal solution to the leftmost one problem as a basic subroutine. Consider a binary image pretiled onto a mesh with multiple broadcasting of size root n x root n one pixel per processor. Our first contribution is to prove an Omega(n(1/6)) time lower bound for the problem of deciding whether the image contains at least one black pixel. We then obtain time lower bounds for many other digital geometry problems by reducing this fundamental problem to all the other problems of interest. Specifically the problems that we address are: detecting whether an image contains at least one black pixel, computing the convex hull of the image, computing the diameter of an image, deciding whether a set of digital points is a digital line, computing the minimum distance between two images, deciding whether two images are linearly separable, computing the perimeter, area and width of a given image. Our second contribution is to show that the time lower bounds obtained are tight by exhibiting simple O(n(1/6)) time algorithms for these problems. As previously mentioned, an interesting feature of these algorithms is that they use, directly or indirectly, an algorithm for the leftmost one problem recently developed by one of the authors.

关键词： MESHES MESHES WITH MULTIPLE BROADCASTING PARALLEL algorithms time-optimal algorithms LEFTMOST ONE DIGITAL GEOMETRY IMAGE PROCESSING PATTERN RECOGNITION MORPHOLOGY

来源：评论

学校读者我要写书评

暂无评论

time-optimal tree computations on sparse meshes

引用

DISCRETE APPLIED MATHEMATICS 1997年第3期77卷 201-220页

作者： Bhagavathi, D Bokka, V Gurla, H Olariu, S Schwing, JL OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 SO ILLINOIS UNIV DEPT COMP SCIEDWARDSVILLEIL 62026

The main goal of this work is to fathom the suitability of the mesh with multiple broadcasting architecture (MMB) for some tree-related computations. We view our contribution at two levels: on the one hand, we exhibit time lower bounds for a number of tree-related problems on the MMB. On the other hand, we show that these lower bounds are tight by exhibiting time-optimal tree algorithms on the MMB. Specifically, we show that the task of encoding and/or decoding n-node binary and ordered trees cannot be solved faster than Omega(log n) time even if the MMB has an infinite number of processors. We then go on to show that this lower bound is tight. We also show that the task of reconstructing n-node binary trees and ordered trees from their traversals can be performed in O(1) time on the same architecture. Our algorithms rely on novel time-optimal algorithms on sequences of parentheses that we also develop.

关键词： meshes with multiple broadcasting binary trees ordered trees encoding decoding traversals tree reconstruction parentheses matching parallel algorithms time-optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A time-optimal solution to a classification problem in ordered functional domains, with applications

引用

PATTERN RECOGNITION 1997年第9期30卷 1555-1564页

作者： Bokka, V Olariu, S Schwing, JL Wilson, L Zomaya, A OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 UNIV WESTERN AUSTRALIA DEPT ELECT & ELECT ENGNPERTHWA 6007AUSTRALIA

Consider a family C of classifiers represented by continuous functions stored, in discretized form, one function per processor in one column of a mesh with multiple broadcasting of size root n x root n. In a number of contexts in pattern recognition, morphology, and knowledge engineering applications, it is necessary to answer point location queries with respect to the given classifiers. The main contribution of this work is to show that in such a domain a collection of m (1 less than or equal to m less than or equal to n), point location (i.e. classification) queries can be answered in Theta(m/root n) time. As it turns out, this is best possible on this platform. (C) 1997 Pattern Recognition Society. Published by Elsevier Science Ltd.

关键词： point location query processing classifiers pattern recognition enhanced meshes time-optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

time-optimal domain-specific querying on enhanced meshes

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第1期8卷 13-24页

作者： Bokka, V Gurla, H Olariu, S Schwing, JL Wilson, L Department of Computer Science Old Dominion University Norfolk VA USA

Query processing is a crucial component of various application domains including information retrieval, database design and management, pattern recognition, robotics, and VLSI. Many of these applications involve data stored in a matrix satisfying a number of properties. One property that occurs time and again specifies that the rows and the columns of the matrix are independently sorted. It is customary to refer to such a matrix as sorted. An instance of the Batched Searching and Ranking problem, (BSR, for short) involves a sorted matrix A of items from a totally ordered universe, along with a collection Q of queries. Q is an arbitrary mix of the following query types: For a search query q(j), one is interested in an item of A that is closest to q(j);for a rank query q(j) one is interested in the number of items of A that are strictly smaller than q(j). The BSR problem asks for solving all queries in Q. In this work, we consider the BSR problem in the following context: The matrix A is pretiled, one item per processor, onto an enhanced mesh of size root n x root n;the m queries are stored, one per processor, in the first m/root n columns of the platform. Our main contribution is twofold. First, we show that any algorithm that solves the BSR problem must take at least Omega(max[logn, root m]) time in the worst case. Second, we show that this time lower bound is tight on meshes of size root n x root n enhanced with multiple broadcasting, by exhibiting an algorithm solving the BSR problem in Theta(max[logn, root m]) time on such a platform.

关键词： searching ranking parallel algorithms time-optimal algorithms enhanced meshes VLSI database design pattern recognition robotics

来源：评论

学校读者我要写书评

暂无评论

A time- and cost-optimal algorithm for interlocking sets - With applications

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1996年第10期7卷 1009-1025页

作者： Olariu, S Zomaya, AY UNIV WESTERN AUSTRALIA DEPT ELECT & ELECT ENGNPARALLEL COMP RES LABPERTHWA 6007AUSTRALIA

Given a family I of intervals, two intervals in I interlock if they overlap but neither of them strictly contains the other. A set of intervals in which every two are related in the reflexive transitive closure of the interlock relation is referred to as an interlocking set. The task is determining the maximal interlocking sets of I arises in numerous applications, including traffic control, robot arm manipulation, segmentation of range images, routing, automated surveillance systems, recognizing polygonal configurations, and code generation for parallel machines. Our first contribution is to show that any sequential algorithm that computes the maximal interlocking sets of a family of n intervals must take Omega(n log n) time in the algebraic tree model. Next, we show that any parallel algorithm for this problem must take Omega(log n) time in the CREW model even if an infinite number of processors acid memory cells are available. We then go on to show that both the sequential and the parallel lower bounds are tight by providing matching algorithms running, respectively, in Theta(n log n) sequential time and in Theta(log n) time using n processors in the CREW model. At the same time, ii the endpoints of the intervals are specified in sorted order, our sequential algorithm runs in Theta(n) time, improving the best previously known result. It is interesting to note that even if the endpoints are sorted, Omega(log n) is a time lower bound for solving the problem in the CREW model, regardless of the amount of resources available. As an application of our algorithm for interlocking sets, we obtain a time- and cost-optimal solution to a restricted version of the single row routing problem. The best previously known result for routing a set of n nets without street crossovers runs in O(log n loglog n) time using n processors in the CRCW model. By contrast, our algorithm runs in O(log n) time using n/log n processors in the CREW model, being both time- and cost-optimal.

关键词： circuit design routing CAD VLSI parallel algorithms lower bounds time-optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

CONVEX POLYGON PROBLEMS ON MESHES WITH MULTIPLE BROADCASTING

引用

Parallel Processing Letters 1992年第2N03期2卷 249-256页

作者： D. BHAGAVATHI S. OLARIU J. L. SCHWING J. ZHANG Department of Computer Science Old Dominion University Norfolk VA 23529-0162 USA

We propose time-optimal algorithms for a number of convex polygon problems on meshes with multiple broadcasting. Specifically, we show that on a mesh with multiple broadcasting of size n × n, the task of deciding whether an n-gon is convex, deciding whether two convex n-gons edge-intersect, deciding whether one convex n-gon lies in the interior of another, as well as variants of the tasks of computing the intersection and union of two convex n-gons can be accomplished in Θ( log n) time. We also show that detecting whether two convex n-gons are separable takes O(1) time.

关键词： Polygons convexity containment intersection union separability meshes with multiple broadcasting lower bounds time-optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A UNIFYING LOOK AT SEMIGROUP COMPUTATIONS ON MESHES WITH MULTIPLE BROADCASTING

引用

Parallel Processing Letters 1994年第1N02期4卷 73-82页

作者： D. BHAGAVATHI S. OLARIU W. SHEN L. WILSON Department of Computer Science Southern Illinois University Edwardsville IL 62026 USA Department of Computer Science Old Dominion University Norfolk VA 23529 USA

Given a sequence of m items α 1 , α 2 ,…, α m from a semigroup S with an associative operation ⊕, the semigroup computation problem involves computing α 1 ⊕ α 2 ⊕…⊕ α m . We consider the semigroup computation problem involving m (2≤m≤n) items on a mesh with multiple broadcasting of size . Our contribution is to present the first lower bound and the first time-optimal algorithm which apply to the entire range of m (2≤m≤n). Specifically, we show that any algorithm that solves the semigroup computation problem must take Ω( log m) time if and time for . We then show that our bound is tight by designing an algorithm whose running time matches the lower bound. These results unify and generalize all semigroup lower bounds and algorithms known to the authors.

关键词： Parallel algorithms semigroup computations lower bounds time-optimal algorithms meshes with multiple broadcasting

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：