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 44

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

_id	e671
authors	Bentley, Jon L., Haken, Dorothea and Saxe, James B.
year	1978
title	A General Method for Solving Divide-and-Conquer Recurrences
source	10 p Carnegie Mellon University: December, 1978. includes bibliography.
summary	The complexity of divide-and-conquer algorithms is often described by recurrence relations of the form T(n) = kT(n/c) + f(n). The only method currently available for solving such recurrences consists of solution tables for fixed functions f and varying k and c. In this note the authors describe a unifying method for solving these recurrences that is both general in applicability and easy to apply without the use of large tables
keywords	recursion, algorithms, divide-and-conquer
series	CADline
last changed	2003/06/02 13:58

_id	sigradi2006_e028c
id	sigradi2006_e028c
authors	Griffith, Kenfield; Sass, Larry and Michaud, Dennis
year	2006
title	A strategy for complex-curved building design:Design structure with Bi-lateral contouring as integrally connected ribs
source	SIGraDi 2006 - [Proceedings of the 10th Iberoamerican Congress of Digital Graphics] Santiago de Chile - Chile 21-23 November 2006, pp. 465-469
summary	Shapes in designs created by architects such as Gehry Partners (Shelden, 2002), Foster and Partners, and Kohn Peterson and Fox rely on computational processes for rationalizing complex geometry for building construction. Rationalization is the reduction of a complete geometric shape into discrete components. Unfortunately, for many architects the rationalization is limited reducing solid models to surfaces or data on spread sheets for contractors to follow. Rationalized models produced by the firms listed above do not offer strategies for construction or digital fabrication. For the physical production of CAD description an alternative to the rationalized description is needed. This paper examines the coupling of digital rationalization and digital fabrication with physical mockups (Rich, 1989). Our aim is to explore complex relationships found in early and mid stage design phases when digital fabrication is used to produce design outcomes. Results of our investigation will aid architects and engineers in addressing the complications found in the translation of design models embedded with precision to constructible geometries. We present an algorithmically based approach to design rationalization that supports physical production as well as surface production of desktop models. Our approach is an alternative to conventional rapid prototyping that builds objects by assembly of laterally sliced contours from a solid model. We explored an improved product description for rapid manufacture as bilateral contouring for structure and panelling for strength (Kolarevic, 2003). Infrastructure typically found within aerospace, automotive, and shipbuilding industries, bilateral contouring is an organized matrix of horizontal and vertical interlocking ribs evenly distributed along a surface. These structures are monocoque and semi-monocoque assemblies composed of structural ribs and skinning attached by rivets and adhesives. Alternative, bi-lateral contouring discussed is an interlocking matrix of plywood strips having integral joinery for assembly. Unlike traditional methods of building representations through malleable materials for creating tangible objects (Friedman, 2002), this approach constructs with the implication for building life-size solutions. Three algorithms are presented as examples of rationalized design production with physical results. The first algorithm [Figure 1] deconstructs an initial 2D curved form into ribbed slices to be assembled through integral connections constructed as part of the rib solution. The second algorithm [Figure 2] deconstructs curved forms of greater complexity. The algorithm walks along the surface extracting surface information along horizontal and vertical axes saving surface information resulting in a ribbed structure of slight double curvature. The final algorithm [Figure 3] is expressed as plug-in software for Rhino that deconstructs a design to components for assembly as rib structures. The plug-in also translates geometries to a flatten position for 2D fabrication. The software demonstrates the full scope of the research exploration. Studies published by Dodgson argued that innovation technology (IvT) (Dodgson, Gann, Salter, 2004) helped in solving projects like the Guggenheim in Bilbao, the leaning Tower of Pisa in Italy, and the Millennium Bridge in London. Similarly, the method discussed in this paper will aid in solving physical production problems with complex building forms. References Bentley, P.J. (Ed.). Evolutionary Design by Computers. Morgan Kaufman Publishers Inc. San Francisco, CA, 1-73 Celani, G, (2004) “From simple to complex: using AutoCAD to build generative design systems” in: L. Caldas and J. Duarte (org.) Implementations issues in generative design systems. First Intl. Conference on Design Computing and Cognition, July 2004 Dodgson M, Gann D.M., Salter A, (2004), “Impact of Innovation Technology on Engineering Problem Solving: Lessons from High Profile Public Projects,” Industrial Dynamics, Innovation and Development, 2004 Dristas, (2004) “Design Operators.” Thesis. Massachusetts Institute of Technology, Cambridge, MA, 2004 Friedman, M, (2002), Gehry Talks: Architecture + Practice, Universe Publishing, New York, NY, 2002 Kolarevic, B, (2003), Architecture in the Digital Age: Design and Manufacturing, Spon Press, London, UK, 2003 Opas J, Bochnick H, Tuomi J, (1994), “Manufacturability Analysis as a Part of CAD/CAM Integration”, Intelligent Systems in Design and Manufacturing, 261-292 Rudolph S, Alber R, (2002), “An Evolutionary Approach to the Inverse Problem in Rule-Based Design Representations”, Artificial Intelligence in Design ’02, 329-350 Rich M, (1989), Digital Mockup, American Institute of Aeronautics and Astronautics, Reston, VA, 1989 Schön, D., The Reflective Practitioner: How Professional Think in Action. Basic Books. 1983 Shelden, D, (2003), “Digital Surface Representation and the Constructability of Gehry’s Architecture.” Diss. Massachusetts Institute of Technology, Cambridge, MA, 2003 Smithers T, Conkie A, Doheny J, Logan B, Millington K, (1989), “Design as Intelligent Behaviour: An AI in Design Thesis Programme”, Artificial Intelligence in Design, 293-334 Smithers T, (2002), “Synthesis in Designing”, Artificial Intelligence in Design ’02, 3-24 Stiny, G, (1977), “Ice-ray: a note on the generation of Chinese lattice designs” Environmental and Planning B, volume 4, pp. 89-98
keywords	Digital fabrication; bilateral contouring; integral connection; complex-curve
series	SIGRADI
email
last changed	2016/03/10 09:52

_id	ca8e
authors	Bentley, Jon L.
year	1975
title	Multidimensional Binary Search Trees Used for Associative Searching
source	communications of the ACM September, 1975. vol. 18: pp. 509-517 : ill. includes bibliography.
summary	This paper develops the multidimensional binary search tree (or k-d tree, where k is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The k-d tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an n record file are: insertion, O(log(n)); deletion of the root, O(n(k-1)/k); deletion of a random node, O(n); and optimization (guarantees logarithmic performance of searches), O(n(log(n))). Search algorithms are given for partial match queries with t keys specified [proven maximum running time of O(n(k-t)/k)] and for nearest neighbor queries [empirically observed average running time of O(log n).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that k-d trees could be quite useful in many applications, and examples of potential uses are given
keywords	search, attributes, information, systems, queries, database, intersection, algorithms
series	CADline
last changed	2003/06/02 13:58

_id	8323
authors	Bentley, Jon L.
year	1985
title	Selection -- Programming Pearls
source	communications of the ACM. November, 1985. vol. 28: pp. 1121- 1127 : ill
summary	This column describes selecting the K- smallest member in a set of N elements. A program for the task is derived and its running time is analyzed
keywords	search, programming, algorithms, techniques
series	CADline
last changed	2003/06/02 13:58

_id	ga0217
id	ga0217
authors	Bentley, Katie A.
year	2002
title	Exploring Aesthetic Pattern Formation
source	International Conference on Generative Art
summary	This paper is an exploration of an interdisciplinary nature. Through studies in fine art, pattern formation in nature, and artificial life, a mechanism for the artistic process is presented. Asynchronous updating schemes implemented in cellular automata and pheromonal agent swarms were evolved to produce aesthetic patterns and compared favourably to non-evolved synchronous production methods. The curious adaptive properties of the resulting patterns were investigated.
series	other
email
more	http://www.generativeart.com/
last changed	2003/11/21 15:16

_id	ecaade03_553_149_shea
id	ecaade03_553_149_shea
authors	Shea, K., Aish, R. and Gourtovaia, M.
year	2003
title	Towards Integrated Performance-Based Generative Design Tools
doi	https://doi.org/10.52842/conf.ecaade.2003.553
source	Digital Design [21th eCAADe Conference Proceedings / ISBN 0-9541183-1-6] Graz (Austria) 17-20 September 2003, pp. 553-560
summary	Generative design methods are capable of generating concepts and stimulating solutions based on robust and rigorous models of design conditions, design languages and design performance. The computer now becomes a design generator in addition to its more conventional role as draftsperson, visualizor, data checker and performance analyst. Motivated by the challenge to enable designers to easily develop meaningful input models of design intent to make best use of a structural generative method, this paper describes an initial combination of a generative design tool, eifForm, and an associative modeling system, Custom Objects, through the use of XML models. The current combined use is illustrated through an example involving generation of a set of 20 interrelated roof trusses with seven unique spans initiated by a parametric model of a saddle shaped stadium roof in Custom Objects. The paper concludes with a discussion of the synergies between associative modeling and generative systems and identifies future extensions aimed to exploit these synergies towards integrated performance-based generative design tools.
keywords	Generative design, parametric/associative geometry, advanced CAD tools,performance-based design, computational design
series	eCAADe
email
more	http://www-edc.eng.cam.ac.uk/designsynthesis
last changed	2022/06/07 07:56

_id	3e51
authors	Cerulli, C., Peng, C. and Lawson, B.
year	2001
title	Capturing Histories of Design Processes for Collaborative Building Design Development. Field Trial of the ADS Prototype
source	Proceedings of the Ninth International Conference on Computer Aided Architectural Design Futures [ISBN 0-7923-7023-6] Eindhoven, 8-11 July 2001, pp. 427-437
summary	The ADS Project - Advanced Design Support for the Construction Design Process - builds on the technological results of the previous COMMIT Project to exploit and demonstrate the benefits of a CAD based Design Decision Support System. COMMIT provides a system for storing knowledge about knowledge within the design process. It records design decisions, the actors who take them and the roles they play when doing so. ADS links COMMIT to an existing object-oriented CAD system, MicroStation/J from Bentley Systems. The project focuses on tackling the problem of managing design information without intruding too much on the design process itself. It provides the possibility to effectively link design decisions back to requirements, to gather rationale information for later stages of the building lifecycle, and to gather knowledge of rationale for later projects. The system enables members of the project team, including clients and constructors, to browse and search the recorded project history of decision making both during and after design development. ADS aims to facilitate change towards a more collaborative process in construction design, to improve the effectiveness of decision-making throughout the construction project and to provide clients with the facility to relate design outcomes to design briefs across the whole building life cycle. In this paper we will describe the field trials of the ADS prototype carried out over a three-month period at the Building Design Partnership (BDP) Manchester office. The objective of these trials is to assess the extent, to which the approach underlying ADS enhances the design process, and to gather and document the views and experiences of practitioners. The ADS prototype was previously tested with historical data of real project (Peng, Cerulli et al. 2000). To gather more valuable knowledge about how a Decision Support System like ADS can be used in practice, the testing and evaluation will be extended to a real project, while it is still ongoing. The live case study will look at some phases of the design of a mixed residential and retail development in Leeds, UK, recording project information while it is created. The users’ feedback on the system usability will inform the continuous redevelopment process that will run in parallel to the live case study. The ADS and COMMIT Projects were both funded by EPSRC.
keywords	Design Rationale, Design Support Systems, Usability Evaluation
series	CAAD Futures
email
last changed	2006/11/07 07:22

_id	8805
authors	Flemming, U., Erhan, H.I. and Ozkaya, I.
year	2001
title	Object-Oriented Application Development in CAD
source	Technical Report 48-01-01. Pittsburgh, PA: Carnegie Mellon University, Institute of Complex Engineered Systems
summary	This report describes a graduate interdisciplinary course offered to students in the graduate program of the School of Architecture at Carnegie Mellon and related departments in fall 2000. The motivation was the realization that when commercial CAD (Computer-Aided Design) systems recently switched from procedural application programming languages to object-oriented ones, third-party application must undergo a significant cognitive retooling"; i. e. they must know more than the syntax and semantics of the new programming language to be used and must be able to employ appropriate software development strategies that are appropriate for the new paradigm. especially with respect to the importance of modeling, a distinguishing characteristic of object-oriented programming. The goal of the course was (a) to introduce and test strategies of object-oriented application development in general and in the context of MicroStation, a state-of-the-art commercial CAD package; (b) to develop-as a course team project-an interesting application that gives students practice with these strategies and team work; and (c) to document our approach and findings so that others can learn from them. The strategies introduced were the use-case approach of Jacobson et al. and the complementary object-modeling tools of Rumbaugh that were recently integrated into the Unified Modeling Language UML. The software platform supporting the course comprised MicroStation, JMDL (a superset of Java) and ProjectBank on the CAD side and RationalRose on the modeling side. The application developed by students in the course supports the generation of drawings for remodeling projects from a set of dgn files describing the existing state of the building to be remodeled. The course was supported by a grant and in-kind contributions from Bentley with matching funds from the Pennsylvania Infrastructure Technology Alliance (PITA)."
series	report
email
last changed	2003/04/23 15:50

_id	ddssar0216
id	ddssar0216
authors	Jones, Dennis B.
year	2002
title	The Quantum Matrix:A Three Dimensional Data Integration and Collaboration ToolFor Virtual Environments
source	Timmermans, Harry (Ed.), Sixth Design and Decision Support Systems in Architecture and Urban Planning - Part one: Architecture Proceedings Avegoor, the Netherlands), 2002
summary	If a picture is worth a thousand words, what if they could walk and talk? How would you like to bring a whole new dimension to your ideas; to use visualization to convey a sense of time and motion, to use imagery to give your ideas vividness; to use sound to give them voice and view them threedimensionally. The Matrix allows you to do all of this and much more. The Matrix resembles Rubik’s cube, but its purpose is to store, manage and access data of all types and to view them in three dimensions in virtual environments such as the CAVE and on your desktop. The current version can store, access and view almost anything that is in digital form, including:Text files Pictures Video Clips Sound Files Spreadsheets URL’s HTML pages Databases CAD drawings Gantt Charts Business Graphics VRML modelsExecutable Programs OLE (Object Link & Embedded) The Matrix is a three-dimensional multimedia and document management tool. The Matrix anticipates the convergence of electronic media into one consistent environment for analysis and representation. the Matrix uses VMRL and OpenGL technologies to allow the user to be immersed in their data as withCinerama, IMAX and Virtual Reality Environments. The Matrix allows the user to exercise their creativity by interactively placing and organizing their data three dimensionally and navigating through and viewingdata and documents in 3D (monocular and binocular – stereo). The Matrix user interface is simple to use. Employing the now familiar “drag and drop” method to manage data and documents. Items can be placed into the matrix grid at a user selected matrix cube location. Upon dropping a document on a cube it appears as a mapped image onto the surface. Navigating through the 3D Matrix-space is fun. All navigation uses real-time animation giving you instant feed back as to where you are. Data drilling is as simple as mouse click on a Matrix cube. Double clicking the on an object in the matrix activates that object. Data dreams was an image that preexisted the program by several years. The dream was to create a new way oforganizing and exploring data. The Qube image was created using Microstation by Bentley Systems, Inc. The figure was modeled using Poser by MetaCreations and composited using Adobe Photoshop.
series	DDSS
last changed	2003/08/07 16:36

_id	caadria2013_173
id	caadria2013_173
authors	Mueller, Volker; Drury B. Crawley and Xun Zhou
year	2013
title	Prototype Implementation of a Loosely Coupled Design Performance Optimisation Framework
doi	https://doi.org/10.52842/conf.caadria.2013.675
source	Open Systems: Proceedings of the 18th International Conference on Computer-Aided Architectural Design Research in Asia (CAADRIA 2013) / Singapore 15-18 May 2013, pp. 675-684
summary	Integration of analyses into early design phases poses several challenges. An experimental implementation of an analysis framework in conjunction with an optimization framework ties authoring and analysis tools together under one umbrella. As a prototype it served intensive use-testing in the context of the SmartGeometry 2012 workshop in Troy, NY. In this prototype the data flow uses a mix of proprietary and publicised file formats, exchanged through publicly accessible interfaces. The analysis framework brokers between the parametric authoring tool and the analysis tools. The optimization framework controls the processes between the authoring tool and parametric engine on one side and the optimization algorithm on the other. In addition to some user-implemented analyses inside the parametric design model the prototype makes energy analysis and structural analysis available. The prototype allows testing assumptions about work flow, implementation, usability and general feasibility of the pursued approach.
wos	WOS:000351496100066
keywords	Design-analysis integration, Design refinement, Optimization
series	CAADRIA
email
last changed	2022/06/07 07:58

_id	678e
authors	Aish, Robert
year	1986
title	Three-dimensional Input and Visualization
source	Computer-Aided Architectural Design Futures [CAAD Futures Conference Proceedings / ISBN 0-408-05300-3] Delft (The Netherlands), 18-19 September 1985, pp. 68-84
summary	The aim of this chapter is to investigate techniques by which man-computer interaction could be improved, specifically in the context of architectural applications of CAD. In this application the object being designed is often an assembly of defined components. Even if the building is not actually fabricated from such components, it is usually conceptualized in these terms. In a conventional graphics- based CAD system these components are usually represented by graphical icons which are displayed on the graphics screen and arranged by the user. The system described here consists of three- dimensional modelling elements which the user physically assembles to form his design. Unlike conventional architectural models which are static (i.e. cannot be changed by the users) and passive (i.e. cannot be read by a CAD system), this model is both 'user generated' and 'machine readable'. The user can create, edit and view the model by simple, natural modelling activities and without the need to learn complex operating commands often associated with CAD systems. In particular, the user can view the model, altering his viewpoint and focus of attention in a completely natural way. Conventional computer graphics within an associated CAD system are used to represent the detailed geometry which the different three-dimensional icons may represent. In addition, computer graphics are also used to present the output of the performance attributes of the objects being modelled. In the architectural application described in this chapter an energy- balance evaluation is displayed for a building designed using the modelling device. While this system is not intended to offer a completely free-form input facility it can be considered to be a specialist man-machine interface of particular relevance to architects or engineers.
series	CAAD Futures
email
last changed	2003/11/21 15:15

_id	449f
authors	Aish, Robert
year	2000
title	Collaborative Design using Long Transactions and "Change Merge"
doi	https://doi.org/10.52842/conf.ecaade.2000.107
source	Promise and Reality: State of the Art versus State of Practice in Computing for the Design and Planning Process [18th eCAADe Conference Proceedings / ISBN 0-9523687-6-5] Weimar (Germany) 22-24 June 2000, pp. 107-111
summary	If our goal is implement collaborative engineering across temporal, spatial and discipline dimensions, then it is suggested that we first have to address the necessary pre-requisites, which include both the deployment of "enterprise computing" and an understanding of the computing concepts on which such enterprise systems are based. This paper will consider the following computing concepts and the related concepts in the world of design computing, and discuss how these concepts have been realised in Bentley SystemsÕ ProjectBank collaborative engineering data repository: Computing Concept Related Design Concept Normalisation Model v. Report (or Drawing) Transaction Consistency of Design Long Transaction Parallelisation of Design Change Merge Coordination (synchronisation) Revisions Coordination (synchronisation) While we are most probably familiar with the applications of existing datadase concepts (such as Normalisation and Transaction Management) to the design process, the intent of this paper to focus
series	eCAADe
email
more	http://www.uni-weimar.de/ecaade/
last changed	2022/06/07 07:54

_id	2005_010
id	2005_010
authors	Aish, Robert
year	2005
title	From Intuition to Precision
doi	https://doi.org/10.52842/conf.ecaade.2005.010
source	Digital Design: The Quest for New Paradigms [23nd eCAADe Conference Proceedings / ISBN 0-9541183-3-2] Lisbon (Portugal) 21-24 September 2005, pp. 10-14
summary	Design has been described as making inspire decisions with incomplete information. True, we may use prior knowledge, we may even think we understand the causalites involved, but what really matters is exploration: of new forms, of new materials, and speculation about the response to the resulting effects. Essentially, this exploration has its own dynamics, involving intuition and spontaneity, and without which there is no design. But of course we all know that this is not the whole story. Design is different to 'craft'; to directly 'making' or 'doing'. It necessarily has to be predictive in order to anticipate what the consequence of the 'making' or 'doing' will be. Therefore we inevitably have to counter balance our intuition with a well developed sense of premeditation. We have to be able to reason about future events, about the consequence of something that has not yet being made. There is always going to be an advantage if this reasoning can be achieved with a degree of precision. So how can we progress from intuition to precision? What abstractions can we use to represent, externalize and test the concepts involved? How can we augment the cognitive processes? How can we record the progression of ideas? And, how do we know when we have arrived? Design has a symbiotic relationship with geometry. There are many design issues that are independent of any specific configurations. We might call these “pre-geometric” issues. And having arrived at a particular configuration, there may be many material interpretations of the same geometry. We might call these “post-geometric” issues. But geometry is central to design, and without appropriate geometric understanding, the resulting design will be limited. Geometry has two distinct components, one is a formal descriptive system and the other is a process of subjective evaluation.
series	eCAADe
email
last changed	2022/06/07 07:54

_id	2006_868
id	2006_868
authors	Becker, Mirco
year	2006
title	Branches and Bifurcations - Building a framework for modeling with isosurfaces in Generative Components
doi	https://doi.org/10.52842/conf.ecaade.2006.868
source	Communicating Space(s) [24th eCAADe Conference Proceedings / ISBN 0-9541183-5-9] Volos (Greece) 6-9 September 2006, pp. 868-873
summary	An isosurface is a three-dimensional representation of a constant value of a field function within a given volume. They are normally used in computer graphics to visualize data in fluid dynamics, medical imaging, geophysics, and meteorology. The advantage of isosurfaces is that they can represent all sorts of topologies. That makes them a perfect tool for modeling, branching, forking, and bifurcating objects with smooth transitions. As they work of a field function, the surface is implicit, the polygonization an approximation. This is a good base for coupling performance with precision. The task was to define a set of handles to change and model an isosurface. It had to happen through the modeling of the field function in a way that is rather intuitive but without giving up the precision one is used to have from standard NURBS/BREP modeling. The paper shows how a modeling framework for isosurfaces is implemented as a plug-in for Bentley Systems Generative Components allowing an intuitive way of exploring design variations. The implementation is illustrated with a proof of concept showing a sketch design.
keywords	Isosurface; Polygonization; Scalar field; Marching Cube; Generative Components
series	eCAADe
email
last changed	2022/06/07 07:54

_id	8a27
authors	Bentley, Jon L. and Carruthers, Wendy
year	1980
title	Algorithms for Testing the Inclusion of Points in Polygons
source	Allertorn Conference on Communication, Control and Computing (18th : 1980). (10) p. includes bibliography
summary	Determining whether a given point lies inside or outside a simple polygon is an important problem in many applications, including computer vision systems and computer-assisted political redistricting systems. In this paper the authors give algorithms for inclusion problems that are efficient for polygons that are 'close to convex' in a certain precise sense. An empirical study of polygons that arise in several applications shows that typical polygons are indeed 'close to convex,' and a program implementing the algorithm shows that is extremely efficient on point sets of practical sizes
keywords	point inclusion, polygons, algorithms, computational geometry
series	CADline
last changed	2003/06/02 13:58

_id	8060
authors	Bentley, Jon L. and Kernighan, Brian W.
year	1986
title	GRAP - a Language for Typesetting Graphs
source	communications of the ACM. August, 1986. vol. 29: pp. 782-792 : charts. includes bibliography
summary	The authors describe a system that makes it easy and convenient to describe graphs and to include them as an integral part of the document formatting process
keywords	programming, computer graphics, algorithms, business
series	CADline
last changed	2003/06/02 10:24

_id	a619
authors	Bentley, Jon L. and McGeoch, Catherine C.
year	1985
title	Amortized Analyses of Self-Organizing Sequential Search ; Heuristics Programming Techniques and Data Structures
source	communications of the ACM April, 1985. vol. 28: pp. 404-411 : ill. includes bibliography.
summary	Amortization is used to analyze the heuristics in a worst- case sense. The relative merit of the heuristics in this analysis is different in the probabilistic analyses. Experiments show that the behavior of the heuristics on real data is more closely described by the amortized analyses than by the probabilistic analyses
keywords	economics, analysis, search, heuristics
series	CADline
last changed	2003/06/02 13:58

_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	6050
authors	Bentley, Jon L.
year	1984
title	Algorithm Design Techniques -- Programming Pearls
source	communications of the ACM. September, 1984. vol. 27: pp. 865-871 : ill
summary	The problem arose in one-dimensional pattern recognition: The input is a vector X of N real numbers; the output is the maximum sum found in any contiguous subvector of the input. The problem is when some of the numbers are negative. This column is built around that problem with an emphasis on the algorithms that solve it and the techniques used to design them
keywords	techniques, programming, algorithms, pattern recognition
series	CADline
last changed	2003/06/02 13:58

_id	6118
authors	Bentley, Jon L.
year	1984
title	Code Tuning -- Programming Pearls
source	communications of the ACM. February, 1984. vol. 27: pp. 91-96
summary	Efficiency is one of many problems in programming, and there are many ways to achieve it. This column is about a low-level approach . 'Code tuning' locates the expensive parts of an existing program and then modifies that code to improve its performance
keywords	programming, search, algorithms, techniques
series	CADline
last changed	2003/06/02 13:58

For more results click below: