Browsing by Author "CHANG, RC"

Now showing 1 - 20 of 29

A DISTRIBUTED SHARED-MEMORY SYSTEM WITH SELF-ADJUSTING COHERENCE SCHEME
(1994-07-01)
WANG, HH
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
The performance of distributed shared memory depends on the memory coherence algorithms and the access characteristics of shared data. In this paper, we propose an efficient coherence scheme using multiple coherence algorithms with self-adjusting feature. Our method can dynamically choose a more adaptive coherence algorithm for each variable class and the incorrect classification of shared variables will not affect the performance. We show that for each fixed classification, application programs suffer 5.1%, 4.6%, and 48.9% increases in the average execution time, when compared against the performance of a self-adjusting scheme. Experiments have shown our approach achieving good performance.
AN IMPLEMENTATION OF AN EXTERNAL PAGER INTERFACE ON BSD UNIX
(1995-05-01)
WANG, HH
;
LU, PK
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
We have designed and implemented an external pager facility on the ConvexOS for Convex supercomputers to enhance memory management capability within the kernel. A group of generic interfaces that can be used to construct a memory manager at user level is proposed. Furthermore, a highly modularized subsystem that provides dynamic configuration and portability is presented.
AN INTERACTIVE APPROACH TO PLANNING SNAKE MOTION
(1994-07-01)
LIU, WB
;
KO, MT
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
One of the most challenging research topics in computer animation is to model the motion of living animals, such as snakes. In this paper, we propose a new structure for modeling a snake's body and use an approach called sequential-goal constraints to simulate various motions of snakes. With this model, a snake's motion is simulated by assigning a sequence of control points along the snake's path and scheduling the times at which the snake passes through these points. The velocity of the snake's motion and the type of movement can be adjusted to meet the requirements of various animated scenarios. The outcome of the animation sequence is smooth and realistic.
AN O(N LOG N) MINIMAL SPANNING TREE ALGORITHM FOR N-POINTS IN THE PLANE
(1986)
CHANG, RC
;
LEE, RCT
;
交大名義發表
;
National Chiao Tung University
AN UPPER BOUND FOR THE AVERAGE LENGTH OF THE EUCLIDEAN MINIMUM SPANNING TREE
(1989)
WANG, NYB
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
APPROXIMATING VERTICES OF A CONVEX POLYGON WITH GRID POINTS IN THE POLYGON
(1992)
LEE, HS
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
In this paper, we consider the problem of approximating a vertex of a convex polygon by an integer point in the polygon. We show that the nearest grid point in a convex polygon to a vertex can be found if it exists, or decided to be nonexistent, in time O(n + logl), where l is the diameter of the polygon and a is the number of the polygon's vertices. The underlying technique used in the continued fraction expansion.
COMPUTING THE CONSTRAINED RELATIVE NEIGHBORHOOD GRAPHS AND CONSTRAINED GABRIEL GRAPHS IN EUCLIDEAN PLANE
(1991)
SU, TH
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
The original relative neighborhood graph (RNG) and Gabriel graph (GG) were defined on a vertices set in the plane. In this paper, we will extend this domain to a planar straight-line graph, and call this type of RNG and GG the constrained relative neighborhood graph (CRNG) and the constrained Gabriel graph (CGG) respectively. Given a planar straight-line graph G in the plane, the edges of the CRNG of G(CRNG(G)) satisfy the following two properties: (1) All of the edges in G (called prespecified edges) are included in the CRNG(G) and the remaining edges do not properly intersect with them; (2) If a non-prespecified edge (p,q) belongs to the CRNG(G) then either there does not exist a vertex z such that d(p,z) < d(p,q) and d(q,z) < d(p,q), or if z satisfies the above condition then z must be invisible by p or q (i.e. if you draw the line segments from z to p and q, then at least one of the lines segments crosses a prespecified edge of G). The constrained Gabriel graph is defined similarly. The CRNG and CGG are the extensions of RNG and GG respectively for which one can specify in advance some special or important edges which must be included in the outcome graph. These variants of RNG and GG provide a new application for the original RNG and GG. In this paper, we will show that both CRNG and CGG are subgraphs of the constrained Delaunay triangulation, and propose two optimal algorithms to construct them in THETA-(n log n) time.
COMPUTING THE K-RELATIVE NEIGHBORHOOD GRAPHS IN EUCLIDEAN PLANE
(1991)
SU, TH
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
In this paper, we will propose an O(n5/3log n) algorithm to construct the k-relative neighborhood graph of a n points set in Euclidean plane, for fixed k. Based on this result, the Euclidean bottleneck matching problem can also be solved in the same time complexity. The k-relative neighborhood graph is a generalization of the relative neighborhood graph.
COVERING GRID POINTS IN A CONVEX POLYGON WITH STRAIGHT-LINES
(1992)
LEE, HS
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
We consider the following problem: Find a set of parallel straight lines with equal spacing to hit all m grid points in a closed region bounded by a convex polygon P with n vertices such that size of this set is minimal. We use continued fraction expansions to explore the combinatorial properties of this problem and propose an O(n + log m) approximation algorithm which guarantees finite performance ratio.
FINDING A MAXIMUM SET OF INDEPENDENT CHORDS IN A CIRCLE
(1992-02-14)
CHANG, RC
;
LEE, HS
;
資訊工程學系
;
Department of Computer Science
In this note we propose an O(nm) algorithm for finding a maximum independent set of m chords which are incident to , vertices on a circle. This result can be applied to improving the time complexity of the algorithm for partitioning simple polygons into a minimum number of uniformly monotone polygons.
FINDING ALL SHORTEST-PATH EDGE SEQUENCES ON A CONVEX POLYHEDRON
(1989)
HWANG, YH
;
CHANG, RC
;
TU, HY
;
資訊工程學系
;
Department of Computer Science
FRACTAL PATTERN FOR A BUTTERFLY WING
(1995)
DAI, WK
;
CHANG, RC
;
SHIH, ZC
;
資訊工程學系
;
Department of Computer Science
The texture pattern of a butterfly wing is very complicated but beautiful. We propose a new and effective procedural texture generation approach using the traits of iteration behavior to synthesize the texture patterns of a butterfly wing realistically. Based on the traits of the iteration process, the graphical behaviors near and between attractive fixed points can model the pattern of eyelike spots and riverlike bands, respectively. Some realistic wing patterns are presented to show the effectiveness of this method.
HIPEC - HIGH PERFORMANCE EXTERNAL VIRTUAL MEMORY CACHING
(1994)
LEE, CH
;
CHEN, MC
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
MINIMAL SYNCHRONIZATION OVERHEAD AFFINITY SCHEDULING ALGORITHM FOR SHARED-MEMORY MULTIPROCESSORS
(1995-06-01)
WANG, YM
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
In addition to load balancing and synchronization overhead, affinity is an important consideration for loop scheduling algorithms in modern multiprocessors. Algorithms based on affinity, like affinity scheduling (AFS), do perform better than dynamic algorithms, such as guided self-scheduling (GSS) and trapezoid self-scheduling (TSS). However, there is still room for improvement in affinity scheduling. This paper suggests a modification to AFS which combines the advantages of both GSS and AFS. Experimental results confirm the effectiveness of the proposed modification.
ON CONSTRUCTING THE RELATIVE NEIGHBORHOOD GRAPHS IN EUCLIDEAN K-DIMENSIONAL SPACES
(1991)
SU, TH
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
In this paper, a new algorithm for constructing the relative neighborhood graph(RNG) of an n points set in Euclidean k-dimensional space is presented, for fixed k greater-than-or-equal-to 3. The worst case running time of the algorithm is O(n2-a(k)(log n)1-a(k)), for a(k) = 2-(k+1), which is under the assumption that no three input points form an isosceles triangle. Previous algorithms need O(n2) time. Our algorithm proceeds in two phases. First, a supergraph of RNG with O(n) edges is constructed and then those edges which do not belong to RNG are eliminated.
ON HITTING GRID POINTS IN A CONVEX POLYGON WITH STRAIGHT-LINES
(1991)
LEE, HS
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
We consider the following problem: Find a set of parallel straight lines with equal spacing to hit all m grid points in a dosed region bounded by a convex polygon P with n vertices such that no grid points in a plane fall between two adjacent lines of these parallel lines and size of this set is minimal. We use continued fraction expansions to explore the combinatorial properties of this problem and propose an O(n + logm) approximation algorithm which guarantees finite performance ratio.
ON THE AVERAGE LENGTH OF DELAUNAY TRIANGULATIONS
(1984)
CHANG, RC
;
LEE, RCT
;
資訊工程學系
;
Department of Computer Science
ON THE MINIMALITY OF POLYGON TRIANGULATION
(1990)
CHEN, CY
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simple n-gon is equal to n + 2w - d - 2, where w is the number of holes and d is the maximum number of independent degenerate triangles of the n-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-free n-gon. The algorithm takes O(nlog2n + DK2) time, where D is the maximum number of vertices lying on the same line in the n-gon and K is the number of minimally degenerate triangles of the n-gon.
PERFORMANCE OF FAST FH MFSK SIGNALS IN JAMMED BINARY CHANNELS
(1994-07-01)
SU, YT
;
CHANG, RC
;
電信工程研究所
;
友訊交大聯合研發中心
;
Institute of Communications Engineering
Soft-decision decoded performance of fast frequency-hopped (FH) M-ary FSK signals over partial band noise jammed binary channels is studied. The effects of metrics conversion, quantization, and the presence of regenerative nodes on the system's cutoff rate performance are investigated. It is found that the conversion from an M-ary metric to a binary one suffers only negligible degradations. For communication links without regenerative nodes, as expected, the infinite-bit soft-decision is the optimal metric, followed by finite-bit soft decision and then hard-decision. For those with regenerative nodes, however, the infinite-bit soft-decision is outperformed by the hard-decision, but the finite-bit soft-decision decoder still keeps its edge over the latter. The issue concerning the order of metric conversion and diversity combining is also analyzed. Numerical results indicate that the conclusion obtained by an earlier simulation report addressing a similar design alternative in fading channels is valid for jammed binary channels, as well. That is, the precombining metric conversion technique gives up only minor performance degradations when compared to the more sophisticated postcombining metric conversion technique.
RAY-CAST VOLUME RENDERING ACCELERATED BY INCREMENTAL TRILINEAR INTERPOLATION AND CELL TEMPLATES
(1995)
KE, HR
;
CHANG, RC
;
資訊工程學系
;
Department of Computer Science
Two related ideas for improving the speed of ray-cast volume rendering are studied in this paper. The first is an incremental algorithm for trilinear interpolation, a method commonly used in ray-cast volume rendering to calculate sample values. The incremental algorithm can expedite trilinear interpolation when many samples along a ray are located in one cell. The second is an efficient hybrid volume rendering restricted to parallel projection. In the preprocessing stage, a cell template is created to store the information used by the incremental trilinear interpolation. When a cell is parallel projected, the information is retrieved from the template to compute the cell contribution. Because the algorithm with only one template may cause aliasing, an antialiasing technique exploiting multiple cell templates is proposed. With our method, ray-cast volume rendering can be accelerated considerably.