NDLI: An algorithm to minimally decompose a rectilinear figure into rectangles (abstract only)

Please wait, while we are loading the content...

Conjunctive planning problems with constrained goal interactions

Analysis of heurisitc search models

A methodology for multiple rule system integration and resolutions within a singular knowledge base

An intelligent tutor for high-school algebra

ADVISOR—an expert system for student advisement

An undergraduate curriculum in expert systems design or knowledge engineering

Natural language processing in a Japanese text-to-speech system

Retirement savings plan advisor: a knowledge-based expert system for tax deferred savings investing

An assistance system for UNIX text formatters

Moses: a graphics oriented software development environment

UIG: the User Interface Generator

Design issues and an architecture for a heterogenous multidatabase system

Incremental conceptual clustering from existing databases

Checkpointing strategies for database systems

Interactive digital-simulation laboratory gains special components

A family of conservative codes with block delimiters for decoding without a phase-locked loop

A symbolic computation method of analytic solution of the mixed Direchlet-Neumann-Robin problem for LaPlace's equation

Design of a pictorial knowledgebase

An expert system for bibliographic retrieval using Prolog

A response generation mechanism for an intelligent active assistance system

An approach to automating knowledge acquisition for expert systems: annotated traces→diagnostic heirarchies

Commonsense reasoning in Prolog

Coordinating existing expert systems

Sensitivity problem in dynamic file organization

An algebraic language for graphical query formulation using an extended entity-relationship model

A pegging method for decomposing relations in databases

Heuristic search in networks with modifiable estimate

Improved parallel algorithms for the depth-first search and monotone circuit value problems

Quicksort algorithms with an early exit for sorted subfiles

A very high level language for large-grained data flow

Manifolds: a very high-level conceptual framework of interprocess synchronization and communication

On solving large maximum concurrent flow problems

Formalization of operations and function definitions in a functional programming language for data structures

A pivotal function approach to estimation and prediction for a model of software reliability

A method to improve testing and debugging in robotic programs using attribute grammars

A parallel algorithm for finding a maximum flow in 0-1 networks

A routing algorithm for three stage rearrangeable Clos networks

Improved sorting algorithms for parallel computers

On efficient balanced codes

A computer based model of life transitions

On optimal algorithms for solving bi-valued game trees

Modified M-timed Petri nets in modelling and performance evaluation of systems

Exploring operating system internals with workstations

Concept and synthesis of an operating system nucleus implemented in computer hardware

An extensible static analysis tool for COBOL programs

Infuse: a tool for automatically managing and coordinating source changes in large systems

A multi-language syntax-directed editor

Information for competitive advantage: implications for computer science education

A partnership—school and computer science work experiences: a career component to the curriculum

Brit bits: computer science in British further education

Intelligent computer-based instruction

What is computer literacy: the sham, the imposter, and the misdirected

Examining the problems of computer-based anxiety: a systemic approach

Bringing algorithms to life

Teaching principles of computer programming

Two methods of instruction for an introductory computer programming course: a language oriented vs a non-language oriented method of instruction

The role of truth maintenance in model-based reasoning (abstract only)

Intelligent systems for statistical process control in steel (abstract only)

Manhattanville College expert academic advisor—preliminary report (abstract only)

Liability for malfunction of medical expert systems—why an expert system is like a power saw (abstract only)

ARMS: arbitrary robot modelling system (abstract only)

Project management expert system (abstract only)

Human factors considerations in the design of a multiple source expert system for military applications (abstract only)

The design of a packet capturing system for measuring IEEE802.5 Token-Ring performances (abstract only)

A fourth order spline method for singular two-point boundary value problems (abstract only)

A frame-based approach to hardware verification (abstract only)

A parallel inference engine (PIE) (abstract only)

An algorithm to minimally decompose a rectilinear figure into rectangles (abstract only)

Formal verification of systolic networks using theorem proving techniques (abstract only)

An algebraic approach to multidimensional convolution (abstract only)

A mixed integer mathematical programming model solution using branch and bound techniques (abstract only)

Min-max sort: a simple sorting method (abstract only)

Property computation in Grapple (abstract only)

The theoretical distribution of the Goodman-Kruskal statistic (abstract only)

A relational data model to represent meaning in natural language sentences (abstract only)

Grammatical relational database model (abstract only)

Database prototyping and implementation (abstract only)

Reliable distributed database systems (abstract only)

Inter-relational information and incompleteness in relational databases (abstract only)

Comparative analysis of dBase by students (abstract only)

Space saving key-lock access control system (abstract only)

Logic programming in LISP with controlled search (abstract only)

Integration of problem-solving entities and processing entities in a coherent model; basis of a method of application (abstract only)

Implementing knowledge bases on secondary storage (abstract only)

Toward more efficient and flexible expert systems via database design (abstract only)

MEND (abstract only): a self-improving diagnostic with deep knowledge

A journalistic explanation facility for an expert system shell (abstract only)

Modula-2 input/output procedure using polymorphic and open-ended data type extensions (abstract only)

The adaptability of Ada as a language for expert systems (abstract only)

Simultaneous presentation in text generation (abstract only)

A functional language architecture that supports fine-grain parallelism (extended abstract)

Critique of SIMAN as a programming language (abstract only)

Combining explanation based generalization with the learning of macro operators (abstract only)

In search of heuristics for keyword detection (abstract only): my source of discontent

Information systems as implementations (abstract only)

SLAW (abstract only): a language free environment—future directions and research

Software protection of micro computer software (abstract only)

On the identity of decision support systems (abstract only)

A probabilistic similarity index between binary vectors for questionnaire data analysis (abstract only)

Computation of pressure distribution on the surface of a vehicle (abstract only)

Representation of an arbitrary tubular surface for CAD/CAM (abstract only)

Syntactic approach to image analysis (abstract only)

Image measurement and recognition (abstract only)

Qualitative reasoning about fit (abstract only)

A geometry package in Ada (abstract only)

Shape from projected light grid (abstract only)

A polygon matching problem in computer vision (abstract only)

IGKS (abstract only): an integrated image processing and graphics environment

Using animated color graphics to illustrate software and hardware organizations (abstract only)

Expert systems in lease accounting (abstract only)

PCDEC, an interactive decision table system for personal computers (abstract only)

A comparison of the effects of structured vs. non-structured and modularized vs. non-modularized programs on run time (abstract only)

What is the proper size of a program module? (abstract only)

The design of an applications development system for a laser videodisc workstation (abstract only)

A niche for structured flowcharts (abstract only)

A comparison of two object-oriented design methodologies (abstract only)

Peer group software reviews in university education for software engineering (abstract only)

An expert tutor in the SLAW programming environment (abstract only)

KAOS (abstract only): a knowledge aided operator's system for the VM operator's console

Towards conceptualisation of physical object propositions (abstract only)

Time representation based on knowledge partitioning (abstract only)

Knowledge and reasoning in graph theory research (abstract only)

A multi-agent planning system (abstract only)

Do women fear computers? (abstract only)

Expert-VSim (abstract only): an expert simulation environment

A fuzzy-power factor correction (abstract only)

Robots and management techniques (abstract only)

Lincoln log factory of the future (LIFOF) (abstract only)

The process allocation in parallel interpretation of logic programs (abstract only)

A parallel processing approach to image object labeling problems (abstract only)

Compilers and parallel architectures (abstract only): sequential to parallel mapping strategies

Semantic parallelization (abstract only): a non-standard denotational approach for imperative programs parallelization

Parsing in a multiprocessor environment (abstract only)

Structured techniques for IMIS (Integrated Maintenance Information System) software development—a case study

The changing role of the university computer center (abstract only)

Teaching assembly language on the Macintosh (abstract only)

On the use of personal computers in teaching the principles of concurrent processing (abstract only)

Software engineering at the University of Dayton (abstract only)

Adaptive approaches to structural software testing (abstract only)

Realization of a multi-valued inner product step processor using CCD's (abstract only)

A quaternary complex number CCD adder (abstract only)

A parallel architecture for rapid image generation and analysis (abstract only)

A multiprogramming stand alone systolic data flow machine (abstract only)

On rational solution of the state equation of a finite automation (abstract only)

Computing multiple modulo summation (abstract only): a new algorithm, its VLSI designs and applications

Algorithms for covering and packing and applications to CAD/CAM (abstract only): preliminary results

Algorithms for paths in the lattice of topologies on finite sets (abstract only)

Surviving the many-person dilemna (abstract only)

An expert system for tuning a macroeconometric model (abstract only)

Computer use and grades (abstract only)

Simulating human problem solving which requires successive decisions (abstract only)

A demographic and attitudinal profile of general education students in a CS survey course (abstract only)

Associations of student characteristics to measures of introductory Pascal computer programming achievement for suburban community college students (abstract only)

Conducting a survey of community computer resources (abstract only)

An evaluation of presentation methods for CAL (abstract only)

Predicting success of a beginning computer course using logistic regression (abstract only)

Professional education for secondary computer science (abstract only)

Conducting a survey of computer technology graduates (abstract only)

An expert system for evaluation of sports injuries (abstract only)

Groundwater model selector (abstract only)

An expert system for selecting a development tool (abstract only)

Programming language selector (abstract only)

College guidance counselor (abstract only)

A reconfigurable software style expert system (abstract only)

A distributed measurement technique for an operating ethernet network (abstract only)

Robustness of the destination tag based routing algorithm for the control of unique path networks (abstract only)

On communication software testing (abstract only)

Implementation of a local area network (abstract only)

An approach to parallel architecture modelling (abstract only)

The porting of XINU to the system 370 VM/CMS environment (abstract only)

Load leveling for control of distributed processing systems (abstract only)

An algorithm to minimally decompose a rectilinear figure into rectangles (abstract only)

Content Provider	ACM Digital Library
Author	Stewart, John Shantaram, R.
Abstract	In computer modeling of geometrical objects it is essential to be able to decompose a complex object into easily managed 'primitives'. For example a rectangular block could be considered a primitive in solid geometry modeling and more complex objects with planar faces could be put together with such blocks. A block itself is obtained by sweeping a rectangle in a direction normal to it. Thus solid objects generated by sweeping simple closed polygons ( the so called extrudes) may be obtained by first decomposing the polygon into a union of (not necessarily disjoint) rectangles, extruding them and finally unioning the resulting blocks. Other Boolean operations such as intersection and difference may have to be employed to build a specified object. This is approach used, for example, in GMSOLID - a geometry modeling software package developed at General Motors. See [1].In this paper we develop an algorithm for decomposing a simple rectilinear polygon into a minimal set of non-overlapping rectangles. Here simple means non-self-intersecting and rectilinear denotes that the sides of the polygon are parallel to the coordinate axes. Throughout this paper the term polygon refers to such a polygon. Further applications of such a decomposition are to be found in IC mask-making and pattern generation. See [3], [4]. Minimality is interesting not only from the optimal point of view but also because the solution seems to involve a degree of symmetry of the given polygon. For other algorithms that treat this problem see [2], [5], [6].Our approach to the problem is by means identifying and analyzing the “left turns” in the given polygon. Simply put, the polygon is traversed in a clockwise fashion and each vertex is labeled as a left turn or a right turn. Since the only polygon with no left turns is a rectangle the presence and the configuration of left turns provides a clue to the degree of departure from the desired final decomposition consisting only of rectangles. The left turns are eliminated by adding edges to the interior of the polygon in a fashion such that the addition of an edge decreases the number of left turns. The problem is thus reduced to the determination of the smallest number of edges which results in only right turns. This is accomplished by classifying edges into three categories labeled DLT, SLT and NLT. It is then shown that the minimum decomposition is achieved by choosing the largest set of mutually non-intersecting DLT edges. An efficient algorithm of complexity O(n**2) is developed to do this. Some implementation remarks are provided.
File Format	PDF
ISBN	0897912187
DOI	10.1145/322917.322985
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1987-02-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in