Cumincad : CUMINCAD Papers : Search Results

Hits 1 to 2 of 2

_id	c0ee
authors	Bentley, Jon L. and Ottmann, Thomas
year	1981
title	The Complexity of Manipulating Hierarchically Defined Sets of Rectangles
source	40 p. : ill. Pittsburgh, PA: Department of Computer Science, CMU., April, 1981. CMU-CS-81-109. includes bibliography
summary	Algorithms that manipulate sets of rectangles are of great practical importance in VLSI design systems and other applications. Although much theoretical work has appeared recently on the complexity of rectangle problems, it has assumed that the inputs are given as a list of rectangles. In this paper the authors study the complexity of rectangle problems when the inputs are given in a hierarchical language that allows the designer to build large designs by replicating small designs. They show that while most of the problems are NP-hard in the general case, there are O(N log N) algorithms that process inputs obeying certain restrictions
keywords	rectangles, algorithms, computational geometry, data structures
series	CADline
last changed	2003/06/02 10:24

_id	c327
authors	Liu, Clive K.
year	1981
title	A Graphic Processor for Computer-Aided Engineering Drawing
source	October, 1981. 7 p
summary	A drafting system whose purpose of is to provide an advanced tool for teaching engineering drawing and as a production tool for designers who regularly produce engineering drawings is described. The graphic processor is part of the system, which incorporates a set of operations that produce and manipulate graphic entities and that require graphic entities as operands. This paper examines the issues of constructing such a processor. Representations are proposed for 2D graphic objects, including points, line segments and segments generated by conic sections; which are predefined data types in the system. The geometric primitive operators take these objects as arguments and produce other graphic objects, and allow users to build up various construction operators and drawings with the same flexibility and generality allowed in, say, descriptive geometry. These operators, which are functions, can be combined as macro expressions that executed by the processor. This environment allows users to define their own macros for various tasks
keywords	CAD, drafting, education, tools
series	CADline
last changed	2003/06/02 13:58

No more hits.