Cumincad : CUMINCAD Papers : Search Results

CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

PDF papers
References

Hits 1 to 20 of 59

Reformat results as: short short into frame detailed detailed into frame

_id	sigradi2009_1044
id	sigradi2009_1044
authors	Cruz, Débora Melo; Gabriela Celani
year	2009
title	A influência de Frank Lloyd Wright sobre João Batista Vilanova Artigas – uma análise formal [The Influence of Frank Lloyd Wright on João Batista Vilanova Artigas - A Formal Analysis]
source	SIGraDi 2009 - Proceedings of the 13th Congress of the Iberoamerican Society of Digital Graphics, Sao Paulo, Brazil, November 16-18, 2009
summary	This study intends to propose a new use of the shape grammar: verify the influence of a certain architect’s language over another architect’s language. Some Brazilian modern architecture critics suggest the existence of an influence of Wright’s prairie houses over Artigas’ early work, but the methods used to reach to this conclusion are always empirical and not very objective. The present work aims to confirm this influence in a more rational manner, comparing Wright’s prairie houses grammar developed by Koning and Eizenberg (1981) to Artigas’ first phase grammar that will developed in this work.
keywords	Gramática da forma; F. L. Wright; J. V. Artigas
series	SIGRADI
email
last changed	2016/03/10 09:49

_id	2f1a
authors	Dabney, M.K., Wright, J.C. and Sanders, D.H.
year	1999
title	Virtual Reality and the Future of Publishing Archaeological Excavations: the multimedia publication of the prehistoric settlement on Tsoungiza at Ancient Nemea
source	New York: The Metropolitan Museum of Art
summary	The Nemea Valley Archaeological Project is a study of settlement and land use in a regional valley system in Greece extending from the Upper Paleolithic until the present. Active field research was conducted by four teams between 1981 and 1990. The first component was a regional archaeological survey. Second, and closely related to the first, was a social anthropological study of modern settlement and land use. Next was a team assigned to excavate the succession of prehistoric settlements of Ancient Nemea on Tsoungiza. Last, historical ecologists, a palynologist, and a geologist formed the environmental component of the research. As a result of advances in electronic publishing, plans for the final publication of the Nemea Valley Archaeological Project have evolved. Complete publication of the excavation of the prehistoric settlements of Ancient Nemea on Tsoungiza will appear in an interactive multimedia format on CD/DVD in Fall 2000. This project is planned to be the first electronic publication of the American School of Classical Studies at Athens. We have chosen to publish in electronic format because it will meet the needs and interests of a wider audience, including avocational archaeologists, advanced high school and college students, graduate students, and professional archaeologists. The multimedia format on CD/DVD will permit the inclusion of text, databases, color and black-and-white images, two and three-dimensional graphics, and videos. This publication is being developed in cooperation with Learning Sites, Inc., which specializes in interactive three-dimensional reconstructions of ancient worlds http://www.learningsites.com. The Nemea Valley Archaeological Project is particularly well prepared for the shift towards electronic publishing because the project's field records were designed for and entered in computer databases from the inception of the project. Attention to recording precise locational information for all excavated objects enables us to place reconstructions of objects in their reconstructed architectural settings. Three-dimensional images of architectural remains and associated features will appear both as excavated and as reconstructed. Viewers will be able to navigate these images through the use of virtual reality. Viewers will also be able to reference all original drawings, photographs, and descriptions of the reconstructed architecture and objects. In this way a large audience will be able to view architectural remains, artifacts, and information that are otherwise inaccessible.
series	other
last changed	2003/04/23 15:14

_id	ecca
authors	Koning, H. and Eizenberg, J.
year	1981
title	The Language of the Prairie : Frank Lloyd Wright's Prairie Houses
source	Environment and Planning B. 1981. vol. 8: pp. 295-323 : ill. includes bibliography
summary	The following parametric shape grammar generates the compositional forms and specifies the function zones of Frank Lloyd Wright's prairie-style houses. The establishment of a fireplace is the key to the definition of the prairie-style house. Around this fireplace, functionally distinguished Froebelean-type blocks are recursively added and interpenetrated to from the basic compositions from which elaborated prairie-style houses are derived. The grammar is based on a corpus of eleven houses from the Winslow house, the evolutionary precursor of the style, to the Robie house, considered by many as the culmination of the style. Much has been written about prairie-style houses - their balance, their debt to Beaux Arts and Japanese design traditions, and their organic qualities. However, such descriptions do not explicitly inform us as to how prairie-style houses are constructed, and consequently provide little help in designing new members of this style. The power of a grammar, such as the one given here, is that it establishes a recursive structure from which new designs can be constructed. Three new prairie houses generated by the grammar as well as step-by-step generation of one of these designs are shown
keywords	synthesis, analysis, architecture, shape grammars, parametrization,
series	CADline
last changed	2003/06/02 13:58

_id	a6f1
authors	Bridges, A.H.
year	1986
title	Any Progress in Systematic Design?
source	Computer-Aided Architectural Design Futures [CAAD Futures Conference Proceedings / ISBN 0-408-05300-3] Delft (The Netherlands), 18-19 September 1985, pp. 5-15
summary	In order to discuss this question it is necessary to reflect awhile on design methods in general. The usual categorization discusses 'generations' of design methods, but Levy (1981) proposes an alternative approach. He identifies five paradigm shifts during the course of the twentieth century which have influenced design methods debate. The first paradigm shift was achieved by 1920, when concern with industrial arts could be seen to have replaced concern with craftsmanship. The second shift, occurring in the early 1930s, resulted in the conception of a design profession. The third happened in the 1950s, when the design methods debate emerged; the fourth took place around 1970 and saw the establishment of 'design research'. Now, in the 1980s, we are going through the fifth paradigm shift, associated with the adoption of a holistic approach to design theory and with the emergence of the concept of design ideology. A major point in Levy's paper was the observation that most of these paradigm shifts were associated with radical social reforms or political upheavals. For instance, we may associate concern about public participation with the 1970s shift and the possible use (or misuse) of knowledge, information and power with the 1980s shift. What has emerged, however, from the work of colleagues engaged since the 1970s in attempting to underpin the practice of design with a coherent body of design theory is increasing evidence of the fundamental nature of a person's engagement with the design activity. This includes evidence of the existence of two distinctive modes of thought, one of which can be described as cognitive modelling and the other which can be described as rational thinking. Cognitive modelling is imagining, seeing in the mind's eye. Rational thinking is linguistic thinking, engaging in a form of internal debate. Cognitive modelling is externalized through action, and through the construction of external representations, especially drawings. Rational thinking is externalized through verbal language and, more formally, through mathematical and scientific notations. Cognitive modelling is analogic, presentational, holistic, integrative and based upon pattern recognition and pattern manipulation. Rational thinking is digital, sequential, analytical, explicatory and based upon categorization and logical inference. There is some relationship between the evidence for two distinctive modes of thought and the evidence of specialization in cerebral hemispheres (Cross, 1984). Design methods have tended to focus upon the rational aspects of design and have, therefore, neglected the cognitive aspects. By recognizing that there are peculiar 'designerly' ways of thinking combining both types of thought process used to perceive, construct and comprehend design representations mentally and then transform them into an external manifestation current work in design theory is promising at last to have some relevance to design practice.
series	CAAD Futures
email
last changed	2003/11/21 15:16

_id	a5c3
authors	Er, M.C.
year	1981
title	The Relations of the Computation of Fibonnaci Numbers with the Polyphase Sort
source	8 p. Wollongong: Department of Computing Science, University of Wollongong, September, 1981. includes bibliography
summary	The theory of polyphase sort has simplified the mathematical derivations of Wilson and Shortt's (1980) algorithm, and offered an intuitive explanation of why Gries and Levin's (1980), and Urbanek's (1980) algorithms work. The computation of order-k Fibonacci numbers is equivalent to moving a window of matrix upwards in a series of ideal distributions
keywords	Fibonacci, sorting, mathematics, algorithms
series	CADline
last changed	2003/06/02 13:58

_id	6758
authors	Flemming, Ulrich
year	1981
title	The Secret of the Casa Giuliani Frigerio
source	Environment and Planning B. 1981. vol. 8: pp. 87-96 : ill. includes bibliography
summary	Basic formal characteristics of Terragni's Casa Giuliani Frigerio are explained by means of a parametric shape grammar
keywords	applications, shape grammars, architecture
series	CADline
email
last changed	2003/02/26 17:24

_id	61ed
authors	Hofstadter, Douglas R.
year	1981
title	Metamagical Themas
source	Scientific American. march, 1981. vol. 244: pp. 20-39. includes ill
summary	The Rubik's Cube is much more than just a puzzle. It is a mechanical invention, a pastime, a learning tool, a source of metaphors, an inspiration. This article discusses the mechanical problems of the Magic Cube
keywords	algorithms, intuition
series	CADline
last changed	2003/06/02 13:58

_id	acadia03_052
id	acadia03_052
authors	Juyal, M., Kensek, K. and Knowles, R.
year	2003
title	SolCAD: 3D Spatial Design Tool Tool to Generate Solar Envelope
source	Connecting >> Crossroads of Digital Discourse [Proceedings of the 2003 Annual Conference of the Association for Computer Aided Design In Architecture / ISBN 1-880250-12-8] Indianapolis (Indiana) 24-27 October 2003, pp. 411-419
doi	https://doi.org/10.52842/conf.acadia.2003.411
summary	In this research the concept of Solar Envelope has been used to develop a 3D Spatial Design Tool tool, SolCAD, for generating an envelope over a given site based on various design parameters. The solar envelope can be imagined as a container, whose boundaries are derived from the sun’s relative motion. Buildings within this container will not overshadow their surroundings during critical periods of solar access for passive and low-energy architecture. The solar envelope is a space-time construct. Its spatial limits are defined by the parameters of land parcel size, shape, orientation, topography and latitude. It also depends on the time or the period of the time for which it is designed. Its time limits are defined by the hours of each day and the season for which solar access is provided to the land parcel (Knowles 1981). This tool intends to generate an envelope over a site of any shape, size and orientation and for different boundary and height conditions of shadow lines. It is suitable for initial stages of building design process to determine the shape of the building even before the design has been conceptualized.
series	ACADIA
email
last changed	2022/06/07 07:52

_id	acadia23_v3_211
id	acadia23_v3_211
authors	Kataw, Hanan
year	2023
title	ACADIA’s Open Call: Expanding the Narrative of Diversity and Inclusion in Computational Design
source	ACADIA 2023: Habits of the Anthropocene: Scarcity and Abundance in a Post-Material Economy [Volume 3: Proceedings of the 43rd Annual Conference for the Association for Computer Aided Design in Architecture (ACADIA) ISBN 979-8-9891764-1-0]. Denver. 26-28 October 2023. edited by A. Crawford, N. Diniz, R. Beckett, J. Vanucchi, M. Swackhamer 24-32.
summary	The Association for Computer Aided Design in Architecture (ACADIA) was founded on October 17, 1981. The first meeting was held at Carnegie-Mellon University and attended by 24 founding members. When the history of ACADIA is discussed, out of these two dozen founders, three are frequently noted: William Mitchell, Charles Eastman, and Chris Yessios. Mitchell was a pioneer in computer-aided design and smart cities research and is, as Wassim Jabi, ACADIA’s 21st president put it, “one of ACADIA’s most famous founding members.”1 Eastman was not only ACADIA’s first president, but also one of the leading figures in the history of Building Information Modeling (BIM) and is often referred to as “the father of BIM.” Yessios is widely known for his work at Ohio State University and his role in developing Form.Z.
series	ACADIA
email
last changed	2024/04/17 14:00

_id	caadria2006_217
id	caadria2006_217
authors	KILIAN, AXEL
year	2006
title	DESIGN EXPLORATION WITH CIRCULAR DEPENDENCIES: A chair design experiment
source	CAADRIA 2006 [Proceedings of the 11th International Conference on Computer Aided Architectural Design Research in Asia] Kumamoto (Japan) March 30th - April 2nd 2006, 217-226
doi	https://doi.org/10.52842/conf.caadria.2006.x.q2e
summary	The paper demonstrates the need for advanced models of representation for circular dependency networks common in design problems that deal with multiple constraints. Constraints in a design problem are generally perceived as limitations to design exploration. The careful construction of constraint relationships can help to turn constraints into design drivers for the problem instead. Closely related to the notion that new goals may emerge from creating designs is the idea that one goal of planning may be the design activity itself (Simon 1981). The interplay of many constraints can lead to circular dependencies that make design exploration a challenge as any change causes ripples throughout the entire design construct. D’Arcy Thompson (1942) describes form as a diagram of forces. The construction of design representations that reflect such dependency networks pose a challenge and are far from exact matches of the task environment (Simon 1981). The paper proceeds in mapping these abstract observations of the circular dependencies in the design process to a chair experiment from design to fabrication giving detailed descriptions of the interdependencies of material, fabrication and aesthetic constraints. The experiment shows how those constraints were instrumental in achieving the aesthetics of the full scale prototype.
series	CAADRIA
type	normal paper
email
last changed	2022/06/07 07:49

_id	16c7
authors	Li, Andrew I-Kang
year	2000
title	Integrating Symbolic and Spatial Information in Shape Grammars, with an Example from Traditional Chinese Architecture
source	CAADRIA 2000 [Proceedings of the Fifth Conference on Computer Aided Architectural Design Research in Asia / ISBN 981-04-2491-4] Singapore 18-19 May 2000, pp. 245-253
doi	https://doi.org/10.52842/conf.caadria.2000.245
summary	Stiny's (1981) formulation of descriptions is applied to building sections and their descriptions found in the twelfth-century Chinese building manual Yingzao fashi.
series	CAADRIA
email
last changed	2022/06/07 07:50

_id	e56f
authors	Milne, Murry, Liggett, Robin S. and Campbell, Carol-Lynn (et al)
year	1981
title	An Interactive Computer Graphic Daylighting Design Tool
source	1981? pp. 99-103: graphs. includes bibliography
summary	A fast simple interactive computer program which plots daylight curves has been developed for hands-on use by architects at the beginning of the design process. It calculates daylight illuminations levels using the well known IES/LOF method. The most important feature of the program is its friendly interface, which means that designers with no computer literacy can easily describe their building and quickly progress through as many design modifications as desired. The program is self-instructional, giving first-time users a demonstration of its various features, then inviting them to go back and put their own building. The program is written in FORTRAN IV and runs on Tektronix storage tube graphics terminal
keywords	evaluation, analysis, algorithms, computer graphics, lighting, user interface
series	CADline
email
last changed	2003/06/02 13:58

_id	sigradi2008_166
id	sigradi2008_166
authors	Papanikolaou, Dimitris
year	2008
title	Digital Fabrication Production System Theory: Towards an Integrated Environment for Design and Production of Assemblies
source	SIGraDi 2008 - [Proceedings of the 12th Iberoamerican Congress of Digital Graphics] La Habana - Cuba 1-5 December 2008
summary	A Digital Fabrication Production System (DFPS) is a concept describing a set of processes, tools, and resources that will be able to produce an artifact according to a design, fast, cheap, and easy, independently of location. A DFPS project is a complex assembly of custom parts that is delivered by a network of fabrication and assembly processes. This network is called the value chain. The workflow concept of a DFPS is the following: begin design process with a custom geometric form; decompose it into constructible parts; send the part files for fabrication to various locations; transport all parts at the construction site at the right time; finally, assemble the final artifact. Conceptually it means that based on a well structured value chain we could build anything we want, at anyplace, at controllable cost and quality. The goals of a DFPS are the following: custom shapes, controllable lead time, controllable quality, controllable cost, easiness of fabrication, and easiness of assembly. Simply stated this means to build any form, anywhere, accurately, cheap, fast, and easy. Unfortunately, the reality with current Digital Fabrication (DF) projects is rather disappointing: They take more time than what was planned, they get more expensive than what was expected, they involve great risk and uncertainty, and finally they are too complex to plan, understand, and manage. Moreover, most of these problems are discovered during production when it is already late for correction. However, there is currently no systematic approach to evaluate difficulty of production of DF projects in Architecture. Most of current risk assessment methods are based on experience gathered from previous similar cases. But it is the premise of mass customization that projects can be radically different. Assembly incompatibilities are currently addressed by building physical mockups. But physical mockups cause a significant loss in both time and cost. All these problems suggest that an introduction of a DFPS for mass customization in architecture needs first an integrated theory of assembly and management control. Evaluating feasibility of a DF project has two main problems: first, how to evaluate assemblability of the design; second, how to evaluate performance of the value chain. Assemblability is a system’s structure problem, while performance is a system’s dynamics problem. Structure of systems has been studied in the field of Systems Engineering by Network Analysis methods such as the Design Structure Matrix (DSM) (Steward 1981), and the liaison graph (Whitney 2004), while dynamics of systems have been studied by System Dynamics (Forrester 1961). Can we define a formal method to evaluate the difficulty of production of an artifact if we know the artifact’s design and the production system’s structure? This paper formulates Attribute Process Methodology (APM); a method for assessing feasibility of a DFPS project that combines Network Analysis to evaluate assemblability of the design with System Dynamics to evaluate performance of the value chain.
keywords	Digital Fabrication, Production System, System Dynamics, Network Analysis, Assembly
series	SIGRADI
email
last changed	2016/03/10 09:57

_id	2c6a
authors	Rosenbloom, Paul S.
year	1981
title	A World-Championship-Level Othello Program
source	Pittsburgh, PA: Department of Computer Science, CMU, August, 1981. [4], 47 p. : ill. and graphs. include bibliography
summary	Othello is a recent addition to the collection of games that have been examined within artificial intelligence. Advances have been rapid, yielding programs that have reached the level of world-championship play. This article describes the current champion Othello program, Iago. The work described here includes: (1) a task analysis of Othello; (2) the implementation of a program based on this analysis and state- of-the-art AI game-playing techniques; and (3) an evaluation of the program's performance through games played against other programs and comparisons with expert human play
keywords	AI, programming, games, systems
series	CADline
last changed	2003/06/02 10:24

_id	1d30
authors	Simon, H.
year	1981
title	The Sciences of the Artificial
source	MIT Press, Cambridge
summary	Continuing his exploration of the organization of complexity and the science of design, this new edition of Herbert Simon's classic work on artificial intelligence adds a chapter that sorts out the current themes and tools -- chaos, adaptive systems, genetic algorithms -- for analyzing complexity and complex systems. There are updates throughout the book as well. These take into account important advances in cognitive psychology and the science of design while confirming and extending the book's basic thesis: that a physical symbol system has the necessary and sufficient means for intelligent action. The chapter "Economic Reality" has also been revised to reflect a change in emphasis in Simon's thinking about the respective roles of organizations and markets in economic systems.
series	other
last changed	2003/04/23 15:14

_id	avocaad_2001_09
id	avocaad_2001_09
authors	Yu-Tung Liu, Yung-Ching Yeh, Sheng-Cheng Shih
year	2001
title	Digital Architecture in CAD studio and Internet-based competition
source	AVOCAAD - ADDED VALUE OF COMPUTER AIDED ARCHITECTURAL DESIGN, Nys Koenraad, Provoost Tom, Verbeke Johan, Verleye Johan (Eds.), (2001) Hogeschool voor Wetenschap en Kunst - Departement Architectuur Sint-Lucas, Campus Brussel, ISBN 80-76101-05-1
summary	Architectural design has been changing because of the vast and creative use of computer in different ways. From the viewpoint of designing itself, computer has been used as drawing tools in the latter phase of design (Mitchell 1977; Coyne et al. 1990), presentation and simulation tools in the middle phase (Liu and Bai 2000), and even critical media which triggers creative thinking in the very early phase (Maher et al. 2000; Liu 1999; Won 1999). All the various roles that computer can play have been adopted in a number of professional design corporations and so-called computer-aided design (CAD) studio in schools worldwide (Kvan 1997, 2000; Cheng 1998). The processes and outcomes of design have been continuously developing to capture the movement of the computer age. However, from the viewpoint of social-cultural theories of architecture, the evolvement of design cannot be achieved solely by designers or design processes. Any new idea of design can be accepted socially, culturally and historically only under one condition: The design outcomes could be reviewed and appreciated by critics in the field at the time of its production (Csikszentmihalyi 1986, 1988; Schon and Wiggins 1992; Liu 2000). In other words, aspects of design production (by designers in different design processes) are as critical as those of design appreciation (by critics in different review processes) in the observation of the future trends of architecture.Nevertheless, in the field of architectural design with computer and Internet, that is, so-called computer-aided design computer-mediated design, or internet-based design, most existing studies pay more attentions to producing design in design processes as mentioned above. Relatively few studies focus on how critics act and how they interact with designers in the review processes. Therefore, this study intends to investigate some evolving phenomena of the interaction between design production and appreciation in the environment of computer and Internet.This paper takes a CAD studio and an Internet-based competition as examples. The CAD studio includes 7 master's students and 2 critics, all from the same countries. The Internet-based competition, held in year 2000, includes 206 designers from 43 counties and 26 critics from 11 countries. 3 students and the 2 critics in the CAD studio are the competition participating designers and critics respectively. The methodological steps are as follows: 1. A qualitative analysis: observation and interview of the 3 participants and 2 reviewers who join both the CAD studio and the competition. The 4 analytical criteria are the kinds of presenting media, the kinds of supportive media (such as verbal and gesture/facial data), stages of the review processes, and interaction between the designer and critics. The behavioral data are acquired by recording the design presentation and dialogue within 3 months. 2. A quantitative analysis: statistical analysis of the detailed reviewing data in the CAD studio and the competition. The four 4 analytical factors are the reviewing time, the number of reviewing of the same project, the comparison between different projects, and grades/comments. 3. Both the qualitative and quantitative data are cross analyzed and discussed, based on the theories of design thinking, design production/appreciation, and the appreciative system (Goodman 1978, 1984).The result of this study indicates that the interaction between design production and appreciation during the review processes could differ significantly. The review processes could be either linear or cyclic due to the influences from the kinds of media, the environmental discrepancies between studio and Internet, as well as cognitive thinking/memory capacity. The design production and appreciation seem to be more linear in CAD studio whereas more cyclic in the Internet environment. This distinction coincides with the complementary observations of designing as a linear process (Jones 1970; Simon 1981) or a cyclic movement (Schon and Wiggins 1992). Some phenomena during the two processes are also illustrated in detail in this paper.This study is merely a starting point of the research in design production and appreciation in the computer and network age. The future direction of investigation is to establish a theoretical model for the interaction between design production and appreciation based on current findings. The model is expected to conduct using revised protocol analysis and interviews. The other future research is to explore how design computing creativity emerge from the process of producing and appreciating.
series	AVOCAAD
email
last changed	2005/09/09 10:48

_id	eb23
authors	Akin, Omer
year	1981
title	Efficient Computer-User Interface in Electronic Mail Systems
source	Department of Computer Science, April, 1981. ii, 24 p. includes bibliography
summary	This research explores the question of improving user- computer interface. The approach is one of observing and codifying various parameters that influence the efficiency of interface in the context of electronic mail tasks. In the paper the authors observe 'expert' and 'regular' users of a mail system and analyze the sources of efficiency. It is clear that experts use a different, more specialized, set of commands in performing standard mail tasks. While experts perform these tasks with fewer errors and more 'completely,' it is not clear that they achieve this any faster than regular users. Recommendations for design are made
keywords	user interface, protocol analysis
series	CADline
email
last changed	2003/05/17 10:09

_id	c9dc
authors	Avron, Barr and Feigenbaum, Edward A. (editors)
year	1981
title	The Handbook of Artificial Intelligence
source	xiv, 409 p. Stanford, California: HeurisTech Press., 1981. vol. 1 of 3: includes bibliography p.[365]-388 and indexes
summary	Part 1 of a three volume set that contains some 200 articles on AI. Volume 1 discusses the goals of AI research, the history of the field and the current active areas of research. It explains how the book is organized, and the literature of the field. How to access journal articles and technical reports for further reading
keywords	AI
series	CADline
last changed	2003/06/02 13:58

_id	barakat_theses_eaea2007
id	barakat_theses_eaea2007
authors	Barakat, Husam
year	2008
title	Analytical Study of the Projects of Students in the Architectural Design - Comparision Between Physical and Digital Models
source	Proceedings of the 8th European Architectural Endoscopy Association Conference
summary	Since its foundation in 1981, Architectural faculty has adopted traditional teaching methods for practical subjects such as architectural design and Urban planning. In these subjects, students submitted their projects and exams on (chanson) and (calk) sheets using various drawing tools. Such tools are still in use by students up to date in manually architectural concept presentation. This comes after the students pass a number of subjects related to art and engineering drawing that help the students in gaining drawing representation and rendering skills.
keywords	architectural concept, traditional teaching, computer technology
series	EAEA
email
more	http://info.tuwien.ac.at/eaea
last changed	2008/04/29 20:46

_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

For more results click below: