ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (100,777)
  • 1990-1994  (53,046)
  • 1985-1989  (39,953)
  • 1950-1954  (7,778)
  • Computer Science  (100,777)
Collection
Source
Keywords
Publisher
Years
Year
Journal
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Fast and simple distributed consensus (1994)
    Springer
    Distributed computing 8 (1994), S. 59-64 
    Details
    ISSN: 1432-0452
    Keywords: Byzantine Agreement ; Distributed Consensus ; Distributed systems ; Early stopping ; Fault-tolerance
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary The problem of fault-tolerant agreement is fundamental to distributed computing. When agreement is to be reached in spite of arbitrary behavior by faulty processors, this problem is calledDistributed Consensus. By requiring that the number of faulty processors be $$O(\sqrt n )$$ , wheren is the number of processors in the system, we are able to derive two new protocols forDistributed Consensus. Both are simple and use messages that are only one bit in length, and both provide forearly stopping: the fewer failures there are, the fewer rounds of communication are required. One protocol is optimal with respect to the number of rounds of communication required, and the other is asymptotically optimal with respect to the total number of message bits exchanged.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02280828
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Wait-free linearization with an assertional proof (1994)
    Springer
    Distributed computing 8 (1994), S. 65-80 
    Details
    ISSN: 1432-0452
    Keywords: Linearizable ; Concurrent data object ; Consensus ; Wait-free ; Memory management ; Correctness ; Invariant ; Stability ; Space complexity ; Time complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Given a sequential implementation of an arbitrary data object, a wait-free, linearizable concurrent implementation is constructed with space complexity quadratic in the number of processes. If processes do not concurrently invoke, the amortized time complexity of the invocations is independent of the number of processes. The worst case time complexity is linear in the number of processes. The construction is based on a compare&swap register. The correctness is proved by means of invariants and stability properties. Since it concerns memory reallocation by concurrent processes in a fault-tolerant setting, this proof is highly nontrivial.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02280829
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On multilevel voting (1994)
    Springer
    Distributed computing 8 (1994), S. 39-58 
    Details
    ISSN: 1432-0452
    Keywords: Mutual exclusion ; Multilevel voting ; Quorum ; Coterie ; Availability ; Replication
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary In a distributed system mutual exclusion is often used to maintain consistency when restricted operations are performed. Mechanisms guaranteeing mutual exclusions should be both resilient and efficient. Resiliency implies high resource availability in the face of failures, while efficiency implies low overhead incurred by performing restricted operations. In this paper, we propose and study a general paradigm, called multilevel voting, which provides a general framework to assist in the design of resilient and efficient mutual exclusion mechanisms. The proposed method uses multiple level quorum consensus. Unlike another method based on the use of multiple quorum consensus, the proposed model only contains one type of integrity constraints. This has the benefit of being conceptually simple and easy to reason about. The strong resemblance with the traditional quorum consensus makes it easy for the proposed paradigm to embed any technique based on traditional quorum schemes. We show that the proposed model represents the exact class of coteries. This means that not only does it have all the power of coteries, but also all schemes under the model are correct. Thus, should the need arise, we can interchange two schemes freely without using any extra mechanisms to ensure correctness. We study a number of issues that have impact on performance such as the degree of a multilevel scheme and the order of a coterie. We explain how the model can be extended also to model the schemes for the synchronization of read and write of replicated data. We provide algorithms for the design of multilevel schemes in the context of mutual exclusion and that of read and write of replicated data.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283569
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Efficient detection of a class of stable properties (1994)
    Springer
    Distributed computing 8 (1994), S. 81-91 
    Details
    ISSN: 1432-0452
    Keywords: Distributed algorithms ; Consistent global states ; Distributed snapshots
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We present a general protocol for detecting whether a property holds in a distributed system, where the property is a member of a class of stable properties we call thelocally stable properties. Our protocol is based on a decentralized method for constructing a maximal subset of the local states that are mutually consistent, which in turn is based on a weakened version of vector time stamps. The structure of our protocol lends itself to refinement, and we demonstrate its utility by deriving some specialized property-detection protocols, including two previously-known protocols that are known to be efficient.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02280830
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Efficient algorithms for optimistic crash recovery (1994)
    Springer
    Distributed computing 8 (1994), S. 105-114 
    Details
    ISSN: 1432-0452
    Keywords: Crash recovery ; Optimistic message logging ; Checkpointing ; Rollback recovery ; Distributed algorithm ; Message complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Recovery from transient processor failures can be achieved by using optimistic message logging and checkpointing. The faulty processorsroll back, and some/all of the non-faulty processors also may have to roll back. This paper formulates the rollback problem as a closure problem. A centralized closure algorithm is presented together with two efficient distributed implementations. Several related problems are also considered and distributed algorithms are presented for solving them.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02280832
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Strong stable properties in distributed systems (1994)
    Springer
    Distributed computing 8 (1994), S. 93-103 
    Details
    ISSN: 1432-0452
    Keywords: Distributed systems ; Consistent snapshot ; Strong stable property ; Termination detection ; Deadlock detection ; Distributed garbage collection
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary A stable property in a distributed system is a global property which once true, remains true forever. This paper refines this notion by formally introducing the concept ofstrong stable properties. A strong stable property has the nice property that it can be correctly evaluated on the consistent part of uncoordinated snapshots. Termination and deadlock are shown to be strong stable properties, whereas distributed garbage is not. We also show how to derive a simple generic algorithm for the detection of a strong stable property. The generic algorithm is illustrated by two examples: termination detection and deadlock detection. Incidentally the paper presents a very simple algorithm for termination detection.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02280831
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Reliability versus cost: Design of a probabilistic broadcast algorithm (1994)
    Springer
    Distributed computing 7 (1994), S. 115-127 
    Details
    ISSN: 1432-0452
    Keywords: Broadcast ; Probabilistic ; algorithms ; Reliability ; Random diffusion ; Geometric topology
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We propose a probabilistic algorithm to solve the problem of distributed broadcast. A simple diffusion algorithm is introduced, and its reliability is evaluated. The cost and reliability of the probabilistic algorithm are compared with the corresponding deterministic algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02277856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Decidability of the termination problem for completely specified protocols (1994)
    Springer
    Distributed computing 7 (1994), S. 129-135 
    Details
    ISSN: 1432-0452
    Keywords: Communicating Finite State Machines ; Termination detection ; Completely specified protocols ; Higman's Lemma
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary In this paper, we present a new class of protocols called completely specified protocols. Each protocol is represented as a system of Communicating Finite State Machines. The class of completely specified protocols is such that each message that can be received by a Finite State Machine, can also be received in every local state of the Finite State Machine. These protocols are important because they allow for modelling unbounded fifo channels and make it possible to decide the Termination Problem, that is whether the reachability tree is finite or not. An example of our techniques is given using a practical problem concerning link protocols.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02277857
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Multi-writer composite registers (1994)
    Springer
    Distributed computing 7 (1994), S. 175-195 
    Details
    ISSN: 1432-0452
    Keywords: Atomicity ; Atomic register ; Composite register ; Concurrency ; Interleaving semantics ; Linearizability ; Shared variable ; Snapshot
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Acomposite register is an array-like shared data object that is partitioned into a number of components. An operation of such a register either writes a value to a single component, or reads the values of all components. A composite register reduces to an ordinary atomic register when there is only one component. In this paper, we show that a composite register with multiple writers per component can be implemented in a wait-free manner from a composite register with a single writer per component. It has been previously shown that registers of the latter kind can be implemented from atomic registers without waiting. Thus, our results establish that any composite register can be implemented in a wait-free manner from atomic registers. We show that our construction has comparable space compexity and better time complexity than other constructions that have been presented in the literature.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02280833
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Towards the construction of distributed detection programs, with an application to distributed termination (1994)
    Springer
    Distributed computing 7 (1994), S. 137-147 
    Details
    ISSN: 1432-0452
    Keywords: Distributed evaluation ; Guarded waves ; Sequence ; Global predicate ; Termination detection
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Methodological design of distributed programs is necessary if one is to master the complexity of parallelism. The class of control programs, whose purpose is to observe or detect properties of an underlying program, plays an important role in distributed computing. The detection of a property generally rests upon consistent evaluations of a predicate; such a predicate can be global, i.e. involve states of several processes and channels of the observed program. Unfortunately, in a distributed system, the consistency of an evaluation cannot be trivially obtained. This is a central problem in distributed evaluations. This paper addresses the problem of distributed evaluation, used as a basic tool for solution of general distributed detection problems. A new evaluation paradigm is put forward, and a general distributed detection program is designed, introducing the iterative scheme ofguarded waves sequence. The case of distributed termination detection is then taken to illustrate the proposed methodological design.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02277858
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    Detecting causal relationships in distributed computations: In search of the holy grail (1994)
    Springer
    Distributed computing 7 (1994), S. 149-174 
    Details
    ISSN: 1432-0452
    Keywords: Distributed computation ; Causality ; Distributed system ; Causal ordering ; Logical time ; Vector time ; Global predicate detection ; Distributed debugging ; Timestamps
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary The paper shows that characterizing the causal relationship between significant events is an important but non-trivial aspect for understanding the behavior of distributed programs. An introduction to the notion of causality and its relation to logical time is given; some fundamental results concerning the characterization of causality are presented. Recent work on the detection of causal relationships in distributed computations is surveyed. The issue of observing distributed computations in a causally consistent way and the basic problems of detecting global predicates are discussed. To illustrate the major difficulties, some typical monitoring and debugging approaches are assessed, and it is demonstrated how their feasibility is severely limited by the fundamental problem to master the complexity of causal relationships.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02277859
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    A fully abstract trace model for dataflow and asynchronous networks (1994)
    Springer
    Distributed computing 7 (1994), S. 197-212 
    Details
    ISSN: 1432-0452
    Keywords: Dataflow networks ; Asynchronous communication ; Semantic models ; Compositionality ; Full abstraction ; Trace semantics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary A dataflow network consists of nodes that communicate over perfect unbounded FIFO channels. For dataflow networks containing only deterministic nodes, a simple and elegant semantic model has been presented by Kahn. However, for nondeterministic networks, the straight-forward generalization of Kahn's model is not compositional. We present a compositional model for nondeterministic networks that is fully abstract i.e., it has added the least amount of extra information to Kahn's model that is necessary for attaining compositionality. The model is based on traces. We also generalize our result, showing that the model is fully abstract also for classes of networks where nodes communicate over other types of asynchronous channels. Examples of such classes are networks with unordered channels, and networks with lossy channels.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02280834
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    Atomicm-register operations (1994)
    Springer
    Distributed computing 7 (1994), S. 213-221 
    Details
    ISSN: 1432-0452
    Keywords: Fault-tolerance ; Shared memory ; Impossibility ; Lower bounds ; Agreement ; Consensus ; Mutual exclusion
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We investigate systems where it is possible to access several shared registers in one atomic step. We characterize those systems in which the consensus problem can be solved in the presence of faults and give bounds on the space required. We also describe a fast solution to the mutual exclusion problem using atomicm-register operations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02280835
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    Adaptive solutions to the mutual exclusion problem (1994)
    Springer
    Distributed computing 8 (1994), S. 1-17 
    Details
    ISSN: 1432-0452
    Keywords: Adaptive algorithms ; Leader election ; Mutual exclusion ; Synchronization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Algorithms for mutual exclusion that adapt to the current degree of contention are developed. Afilter and a leader election algorithm form the basic building blocks. The algorithms achieve system response times that are independent of the total number of processes and governed instead by the current degree of contention. The final algorithm achieves a constant amortized system response time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283567
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    Naming symmetric processes using shared variables (1994)
    Springer
    Distributed computing 8 (1994), S. 19-38 
    Details
    ISSN: 1432-0452
    Keywords: Parallel algorithm ; Randomized protocol ; Synchronization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Implementations of inter-process communication and synchronization in distributed systems usually rely on the existence of unique ids for the processes. We consider the problem of generating such ids for identical processes in a shared-variable system. A randomized protocol that assigns distinct ids to the processes within an expected polynomial number of rounds using a polynomial number of boolean atomic variables is presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283568
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    On the power of randomization in on-line algorithms (1994)
    Springer
    Algorithmica 11 (1994), S. 2-14 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; Competitive analysis ; Randomized algorithms ; Game theory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient “simulation” of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294260
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    Randomized competitive algorithms for the list update problem (1994)
    Springer
    Algorithmica 11 (1994), S. 15-32 
    Details
    ISSN: 1432-0541
    Keywords: Sequential search ; List-update ; On-line algorithms ; Competitive analysis ; Randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294261
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    On-line algorithms for locating checkpoints (1994)
    Springer
    Algorithmica 11 (1994), S. 33-52 
    Details
    ISSN: 1432-0541
    Keywords: Information retrieval ; Data compression ; Servers ; Competitive ratio
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Motivated by applications in data compression, debugging, and physical simulation, we consider the problem of adaptively choosing locations in a long computation at which to save intermediate results. Such checkpoints allow faster recomputation of arbitrary requested points within the computation. We abstract the problem to a server problem in whichk servers move along a line in a single direction, modeling the fact that most computations are not reversible. Since checkpoints may be arbitrarily copied, we allow a server to jump to any location currently occupied by another server. We present on-line algorithms and analyze their competitiveness. We give lower bounds on the competitiveness of any on-line algorithm and show that our algorithms achieve these bounds within relatively small factors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294262
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Coloring inductive graphs on-line (1994)
    Springer
    Algorithmica 11 (1994), S. 53-72 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; Graph coloring ; Inductive graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider the problem of on-line graph coloring. In an instance of on-line graph coloring, the nodes are presented one at a time. As each node is presented, its edges to previously presented nodes are also given. Each node must be assigned a color, different from the colors of its neighbors, before the next node is given. LetA(G) be the number of colors used by algorithmA on a graphG and letx(G) be the chromatic number ofG. The performance ratio of an on-line graph coloring algorithm for a class of graphsC is maxG ∈C(A(G)/χ(G)). We consider the class ofd-inductive graphs. A graphG isd-inductive if the nodes ofG can be numbered so that each node has at mostd edges to higher-numbered nodes. In particular, planar graphs are 5-inductive, and chordal graphs arex(G)-inductive. First Fit is the algorithm that assigns each node the lowest-numbered color possible. We show that ifG isd-inductive, then First Fit usesO(d logn) colors onG. This yields an upper bound ofo(logn) on the performance ratio of First Fit on chordal and planar graphs. First Fit does as well as any on-line algorithm ford-inductive graphs: we show that, for anyd and any on-line graph coloring algorithmA, there is ad-inductive graph that forcesA to use Ω(d logn) colors to colorG. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookaheadl, if it must color nodei after examining only the firstl+i nodes. We show that, forl〈n/logn, the lower bound ofd logn colors still holds.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294263
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    A new measure for the study of on-line algorithms (1994)
    Springer
    Algorithmica 11 (1994), S. 73-91 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; Competitive analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An accepted measure for the performance of an on-line algorithm is the “competitive ratio“ introduced by Sleator and Tarjan. This measure is well motivated and has led to the development of a mathematical theory for on-line algorithms. We investigate the behavior of this measure with respect to memory needs and benefits of lookahead and find some counterintuitive features. We present lower bounds on the size of memory devoted to recording the past. It is also observed that the competitive ratio reflects no improvement in the performance of an on-line algorithm due to any (finite) amount of lookahead. We offer an alternative measure that exhibits a different and, in some respects, more intuitive behavior. In particular, we demonstrate the use of our new measure by analyzing the tradeoff between the amortized cost of on-line algorithms for the paging problem and the amount of lookahead available to them. We also derive on-line algorithms for theK-server problem on any bounded metric space, which, relative to the new measure, are optimal among all on-line algorithms (up to a factor of 2) and are within a factor of 2K from the optimal off-line performance.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294264
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    Dynamic programming and convex clustering (1994)
    Springer
    Algorithmica 11 (1994), S. 93-103 
    Details
    ISSN: 1432-0541
    Keywords: Clustering algorithms ; Dynamic programming ; Pyramidal dissimilarity ; Convex clustering ; Ordering constraint
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper the notion of convexity of clusterings for the given ordering of units is introduced. In the case when at least one (optimal) solution of the clustering problem is convex, dynamic programming leads to a polynomial algorithm with complexityO(kn 3). We prove that, for several criterion functions, convex optimal clusterings exist when dissimilarity is pyramidal for a given ordering of units.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182769
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    A tight lower bound for the worst case of Bottom-Up-Heapsort (1994)
    Springer
    Algorithmica 11 (1994), S. 104-115 
    Details
    ISSN: 1432-0541
    Keywords: Heapsort ; Bottom-Up-Heapsort ; Tight lower bound
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Bottom-Up-Heapsort is a variant of Heapsort. Its worst-case complexity for the number of comparisons is known to be bounded from above by 3/2n logn+0(n), wheren is the number of elements to be sorted. There is also an example of a heap which needs 5/4n logn-0(n log logn) comparisons. We show in this paper that the upper bound is asymptotically tight, i.e., we prove for largen the existence of heaps which need at least 3/2n logn−O(n log logn) comparisons. This result also proves the old conjecture that the best case for classical Heapsort needs only asymptotic n logn + O(n log logn) comparisons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182770
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Algorithms for bichromatic line-segment problems and polyhedral terrains (1994)
    Springer
    Algorithmica 11 (1994), S. 116-132 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Line-segment intersection ; Segment trees ; Lines in space ; Polyhedral terrains ; Deterministic and randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182771
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    Variations on ray shooting (1994)
    Springer
    Algorithmica 11 (1994), S. 133-145 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Half-plane range searching ; ES-trees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We solve some problems related toray shooting in the plane, such as finding the first object hit by a query ray or counting the number of objects intersected by the query line. Our main results are an algorithm for finding the first hit when the objects are lines, and an algorithm for the case when the objects are segments. If the segments form simple polygons, this information can be used for reducing the complexity of the algorithms. The algorithms are efficient in space and in query time. Moreover, they are simple and therefore of practical use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182772
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    Planar geometric location problems (1994)
    Springer
    Algorithmica 11 (1994), S. 185-195 
    Details
    ISSN: 1432-0541
    Keywords: Facility location ; Parametric searching ; Duality ; Planar arrangements
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present anO(n 2 log3 n) algorithm for the two-center problem, in which we are given a setS ofn points in the plane and wish to find two closed disks whose union containsS so that the larger of the two radii is as small as possible. We also give anO(n 2 log5 n) algorithm for solving the two-line-center problem, where we want to find two strips that coverS whose maximum width is as small as possible. The best previous solutions of both problems requireO(n 3) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182774
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    The derivation of on-line algorithms, with an application to finding palindromes (1994)
    Springer
    Algorithmica 11 (1994), S. 146-184 
    Details
    ISSN: 1432-0541
    Keywords: Derivation of on-line algorithms ; Transformational programming ; Bird-Meertens calculus ; Segment problems ; Theory of lists ; Longest palindromic substring ; Maximal palindromes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A theory for the derivation of on-line algorithms is presented. The algorithms are derived in the Bird-Meertens calculus for program transformations. This calculus provides a concise functional notation for algorithms, and a few powerful theorems for proving equalities of functions. The theory for the derivation of on-line algorithms is illustrated with the derivation of an algorithm for finding palindromes. An on-line linear-time random access machine (RAM) algorithm for finding the longest palindromic substring in a string is derived. For the purpose of finding the longest palindromic substring, all maximal palindromic substrings are computed. The list of maximal palindromes obtained in the computation of the longest palindrome can be used for other purposes such as finding the largest palindromic rectangle in a matrix and finding the shortest partition of a string into palindromes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182773
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Editor's foreword (1994)
    Springer
    Algorithmica 11 (1994), S. 197-199 
    Details
    ISSN: 1432-0541
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240732
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    Flow in planar graphs with vertex capacities (1994)
    Springer
    Algorithmica 11 (1994), S. 200-225 
    Details
    ISSN: 1432-0541
    Keywords: Planar graphs ; Vertex capacities ; Network flow ; Circulation problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Max-flow in planar graphs has always been studied with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as edges have capacity constraints. In the context of general graphs considering only edge capacities is not restrictive, since the vertex-capacity problem can be reduced to the edge-capacity problem. However, in the case of planar graphs this reduction does not maintainplanarity and cannot be used. We study different versions of the planar flow problem (all of which have been extensively investigated in the context of edge capacities).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240733
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Tight bounds on the number of minimum-mean cycle cancellations and related results (1994)
    Springer
    Algorithmica 11 (1994), S. 226-242 
    Details
    ISSN: 1432-0541
    Keywords: Network flow problems ; Minimum cost flow ; Minimum cost circulation ; Combinatorial optimization ; Cycle canceling algorithms ; Strongly polynomial algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We prove a tight Θ(min(nm log(nC), nm2)) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations toO(nm 2). We also give an improved version of the maximum-mean cut canceling algorithm of [7], which is a dual of the minimum-mean cycle-canceling algorithm. Our version of the dual algorithm runs in O(nm2) iterations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240734
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs (1994)
    Springer
    Algorithmica 11 (1994), S. 256-277 
    Details
    ISSN: 1432-0541
    Keywords: Minimum-cost flow ; Convex costs ; Multiple arcs ; Networks ; Strongly polynomial algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present two efficient algorithms for the minimum-cost flow problem in which arc costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of linear arc costs. Our first algorithm uses the Edmonds-Karp scaling technique. Its complexity isO(M logU(m+n logM)) for a network withn vertices,m arcs, M linear cost segments, and an upper boundU on the supplies and the capacities. The second algorithm is a strongly polynomial version of the first, and it uses Tardos's idea of contraction. Its complexity isO(M logM(m+n logM)). Both algorithms improve by a factor of at leastM/m the complexity of directly applying existing algorithms to a transformed network in which arc costs are linear.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240736
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    A new scaling algorithm for the maximum mean cut problem (1994)
    Springer
    Algorithmica 11 (1994), S. 243-255 
    Details
    ISSN: 1432-0541
    Keywords: Maximum mean cut ; Scaling algorithm ; Circulation feasibility ; Minimum-cost circulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new scaling algorithm for the maximum mean cut problem. The mean of a cut is defined by the cut capacity divided by the number of arcs crossing the cut. The algorithm uses an approximate binary search and solves the circulation feasibility problem with relaxed capacity bounds. The maximum mean cut problem has recently been studied as a dual analogue of the minimum mean cycle problem in the framework of the minimum cost flow problem by Ervolina and McCormick. A networkN=(G, lower, upper) with lower and upper arc capacities is said to be δ-feasible ifN has a feasible circulation when we relax the capacity bounds by δ; that is, we use (lower(a)- δ, upper(a)+δ) bounds instead of (lower(a), upper(a)) bounds for each arca εA. During an approximate binary search we maintain two bounds,LB andUB, such thatN is LB-infeasible andUB-feasible, and we reduce the interval size (LB, UB) by at least one-third at each iteration. For a graph withn vertices, m arcs, and integer capacities bounded byU, the running time of this algorithm is O(mn log(nU). This time bound is better than the time achieved by McCormick and Ervolina under thesimilarity condition (that is,U=O(no(1))). Our algorithm can be naturally used for the circulation feasibility problem, and thus provides a new scaling algorithm for the minimum cut problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240735
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    A faster parametric minimum-cut algorithm (1994)
    Springer
    Algorithmica 11 (1994), S. 278-290 
    Details
    ISSN: 1432-0541
    Keywords: Network flow ; Cuts ; Parametric cuts ; Graph algorithms ; Layout
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Galloet al. [4] recently examined the problem of computing on line a sequence ofk maximum flows and minimum cuts in a network ofn nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, thek maximum flows and minimum cuts can be computed simply in O(n3+kn2) total time, provided that the capacity changes are made “in order.” Using dynamic trees their time bound isO(nm log(n2/m)+km log(n2/m)). We show how to reduce the total time, using a simple algorithm, to O(n3+kn) for explicitly computing thek minimum cuts and implicitly representing thek flows. Using dynamic trees our bound is O(nm log(n2/m)+kn log(n2/m)). We further reduce the total time toO(n 2√m) ifk is at most O(n). We also apply the ideas from [10] to show that the faster bounds hold even when the capacity changes are not “in order,” provided we only need the minimum cuts; if the flows are required then the times are respectively O(n3+km) and O(n2√m). We illustrate the utility of these results by applying them to therectilinear layout problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240737
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    Network flow and 2-satisfiability (1994)
    Springer
    Algorithmica 11 (1994), S. 291-319 
    Details
    ISSN: 1432-0541
    Keywords: Network flow ; 2-Satisfiability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present two algorithms for network flow on networks with infinite capacities and finite integer supplies and demands. The first algorithm runs inO(m√K) time on networks withm edges, whereK=O(m2/log4 m) is the value of the optimal flow, and can also be applied to the capacitated case by lettingK be the sum of thefinite capacities alone. The second algorithm runs inO(wm logK) time for arbitraryK, where w is a new parameter, thewidth of the network. These algorithms as well as other uses of the notion of width lead to results for several questions on the 2-satisfiability problem: minimizing the weight of a solution, finding the transitive closure, recognizing partial solutions, enumerating all solutions. The results have applications to stable matching, wherew corresponds to the number of people andm to the instance size (usuallym ≈ w2).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240738
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    Algorithms and complexity analysis for some flow problems (1994)
    Springer
    Algorithmica 11 (1994), S. 320-340 
    Details
    ISSN: 1432-0541
    Keywords: Parametric flow ; Constrained flow ; Strongly polynomial time
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Several network-flow problems with additional constraints are considered. They are all special cases of the linear-programming problem and are shown to be ℘-complete. It is shown that the existence of a strongly polynomial-time algorithm for any of these problems implies the existence of such an algorithm for the general linear-programming problem. On the positive side, strongly polynomial algorithms for some parametric flow problems are given, when the number of parameters is fixed. These algorithms are applicable to constrained flow problems when the number of additional constraints is fixed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01240739
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs (1994)
    Springer
    Algorithmica 11 (1994), S. 341-352 
    Details
    ISSN: 1432-0541
    Keywords: Sensitivity analysis ; Minimum spanning tree ; Network optimization ; Planar graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its replacement edges, and to verify its minimality. It can also be used to analyze the sensitivity of a single-source shortest-path tree to changes in edge costs, and to analyze the sensitivity of a minimum-cost network flow. The algorithm is simple and practical. It uses the properties of a planar embedding, combined with a heap-ordered queue data structure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187017
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    On the complexity of preflow-push algorithms for maximum-flow problems (1994)
    Springer
    Algorithmica 11 (1994), S. 353-359 
    Details
    ISSN: 1432-0541
    Keywords: Graph theory ; Network flows ; Algorithms ; Complexity ; Maximum flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs inO(n 2 √m) time. We give a new proof of this fact. We compare our proof with the earlier work by Cheriyan and Maheswari who showed that the largest-label implementation of the preflow-push algorithm of Goldberg and Tarjan runs inO(n 2 √m) time when implemented with current edges. Our proof that the number of nonsaturating pushes isO(n 2 √m), does not rely on implementing pushes with current edges, therefore it is true for a much larger family of largest-label implementation of the preflow-push algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187018
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Visibility with a moving point of view (1994)
    Springer
    Algorithmica 11 (1994), S. 360-378 
    Details
    ISSN: 1432-0541
    Keywords: Hidden line removal ; Terrain ; Flight simulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We investigate three-dimensional visibility problems in which the viewing position moves along a straight flightpath. Specifically we focus on two problems: determining the points along the flightpath at which the topology of the viewed scene changes, and answering ray-shooting queries for rays with origin on the flightpath. Three progressively more specialized problems are considered: general scenes, terrains, and terrains with vertical flightpaths.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187019
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Edge crossings in drawings of bipartite graphs (1994)
    Springer
    Algorithmica 11 (1994), S. 379-403 
    Details
    ISSN: 1432-0541
    Keywords: Graph ; Bipartite graph ; Directed graph ; Edge crossing ; Median
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Systems engineers have recently shown interest in algorithms for drawing directed graphs so that they are easy to understand and remember. Each of the commonly used methods has a step which aims to adjust the drawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimization of the number of arcs in crossings in a bipartite graph. The performance of the commonly employed “barycenter” heuristic for this problem is analyzed. An alternative method, the “median” heuristic, is proposed and analyzed. The new method is shown to compare favorably with the old in terms of performance guarantees. As a bonus, we show that the median heuristic performs well with regard to the total length of the arcs in the drawing.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187020
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    Finding the closed partition of a planar graph (1994)
    Springer
    Algorithmica 11 (1994), S. 443-468 
    Details
    ISSN: 1432-0541
    Keywords: Closed partition ; Compact digraph ; Directed graph ; Dual graph ; Planar graph ; Sequential algorithm ; Strongly connected component
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider the problem of finding aclosed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs inO(mn) time wherem is the number of directed edges andn is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that arecompact. We then build on this algorithm to obtain an O(n1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293266
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Provably good pattern generators for a random pattern test (1994)
    Springer
    Algorithmica 11 (1994), S. 429-442 
    Details
    ISSN: 1432-0541
    Keywords: Random pattern test ; Pairwise independence ; Probability, Random ; Random number generator ; LFSR
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes a pseudorandom pattern generator for the random pattern test of combinational circuits. Suppose that a fractionp of the possible patterns detects some fault and the generator generates L patterns to test the circuit. Then the probability that the generator generates a pattern that tests the fault is at leastpL/(pL + 1). The only assumption is that all values of the seed of the generator are equally likely. The seed is twice as long as a single pattern. The generator is less than twice as expensive as a linear feedback shift register. Thus, it can be used in practice. More complicated generators that achieve a better bound are also discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293265
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    A workbench for computational geometry (1994)
    Springer
    Algorithmica 11 (1994), S. 404-428 
    Details
    ISSN: 1432-0541
    Keywords: Algorithms ; Computational geometry ; Implementation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187021
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    An improved technique for output-sensitive hidden surface removal (1994)
    Springer
    Algorithmica 11 (1994), S. 469-484 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden surface removal ; Ray shooting
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We derive a new output-sensitive algorithm for hidden surface removal in a collection ofn triangles, viewed from a pointz such that they can be ordered in an acyclic fashion according to their nearness toz. Ifk is the combinatorial complexity of the outputvisibility map, then we obtain a sophisticated randomized algorithm that runs in (randomized) timeO(n4/3 log2.89 n +k 3/5 n 4/5 + δ for anyδ 〉 0. The method is based on a new technique for tracing the visible contours using ray shooting.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293267
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    A provably fast linear-expected-time maxima-finding algorithm (1994)
    Springer
    Algorithmica 11 (1994), S. 501-524 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Maxima ; Probabilistic analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a recent paper Bentleyet al. [1] presented some fast (low-multiplicative constants) linear-expected-time algorithms for finding the maxima ofN points chosen independently identically distributed (i.i.d.) from a Component Independent (CI) distribution. They also presented another algorithm, the Move-To-Front (MTF) algorithm, which empirical evidence suggests runs faster than the other algorithms. They conjectured that the MTF algorithm runs inN+o(N) expected time. In this paper we prove their conjecture forN points chosen i.i.d. from any two-dimensional distribution. The proof mixes probabilistic and amortized techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189991
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    Designing secure communication protocols from trust specifications (1994)
    Springer
    Algorithmica 11 (1994), S. 485-499 
    Details
    ISSN: 1432-0541
    Keywords: Very large distributed systems ; Secure communication ; Trust, Channel synthesis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a very large distributed system, entities may trust and mistrust others with respect to communication security in arbitrarily complex ways. We formulate the problem of designing a secure communication protocol, given a network interconnection and a ternary relation which captures trust between the entities. We didentify several important ways of synthesizing secure channels, and study the algorithmic problem of designing a secure communication protocol connecting the entities, given the connectivity of the network and the trust relationship between the nodes. We show that whether secure communication is possible can be decided easily in polynomial time. If we also require that channel synthesis proceed along unambiguous paths (in which case the protocol is defined on a spanning tree of the network), we show that the design problem is NP-complete, and we give a linear-time algorithm for an interesting special case of the problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293268
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    Competitive randomized algorithms for nonuniform problems (1994)
    Springer
    Algorithmica 11 (1994), S. 542-571 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; Competitive analysis ; Randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Competitive analysis is concerned with comparing the performance of on-line algorithms with that of optimal off-line algorithms. In some cases randomization can lead to algorithms with improved performance ratios on worst-case sequences. In this paper we present new randomized on-line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approachinge/(e−1) ≈ 1.58 against an oblivious adversary. These ratios are optimal and are a surprising improvement over the best possible ratio in the deterministic case, which is 2. We also consider the situation when the request sequences for these problems are generated according to an unknown probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have competitive factors approachinge/(e−1). Finally, we obtain randomized algorithms for the 2-server problem on a class of isosceles triangles. These algorithms are optimal against an oblivious adversary and have competitive ratios that approache/(e−1). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189993
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    A deterministicO(k 3)-competitivek-server algorithm for the circle (1994)
    Springer
    Algorithmica 11 (1994), S. 572-578 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; k-Server problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Suppose thatk mobile servers are located on a circle. Repeatedly, a request at a pointx on the circle appears. To serve this request one of the servers has to be moved tox. The cost of moving a server tox is the distance on the circle between the server's previous location andx. The decision which server to move has to be doneon-line; that is, without the knowledge of future requests. We give a deterministic on-line algorithm for making these decisions. Our algorithm isO(k 3)-competitive: for any sequence of requests, the cost incurred by our algorithm in serving this sequence is bounded (up to an additive constant) byO(k 3) times the cost of serving this sequence using the bestoff-line algorithm; i.e., an algorithm that hasa priori knowledge of the whole sequence. Our algorithm is the best deterministic constructive algorithm fork〉2.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189994
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    An optimal algorithm for the on-line closest-pair problem (1994)
    Springer
    Algorithmica 12 (1994), S. 18-29 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Closest pair ; Point location ; Centroid ; Amortization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give an algorithm that computes the closest pair in a set ofn points ink-dimensional space on-line, inO(n logn) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision ofk-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377181
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Point placement algorithms for Delaunay triangulation of polygonal domains (1994)
    Springer
    Algorithmica 12 (1994), S. 1-17 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Polygonal domain ; Finite-element mesh generation ; Edge-free circle ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377180
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    Guest editor's introduction (1994)
    Springer
    Algorithmica 12 (1994), S. 69-71 
    Details
    ISSN: 1432-0541
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185205
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Efficient ray shooting and hidden surface removal (1994)
    Springer
    Algorithmica 12 (1994), S. 30-53 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Multilevel data structures ; Hidden surface removal ; Output-sensitive
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n 2+ɛ) preprocessing, for any fixedɛ 〉 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn 4+ɛ) preprocessing and has a query time ofO(logn). We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any ɛ 〉 0, we can obtain an algorithm with running time $$O(n^{1 + \varepsilon } \sqrt k )$$ , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377182
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    Ray shooting in polygons using geodesic triangulations (1994)
    Springer
    Algorithmica 12 (1994), S. 54-68 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray-shooting ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO(√ logn) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377183
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    Algorithms for parallel memory, II: Hierarchical multilevel memories (1994)
    Springer
    Algorithmica 12 (1994), S. 148-169 
    Details
    ISSN: 1432-0541
    Keywords: Memory hierarchies ; Multilevel memory ; Sorting ; Distribution sort ; FFT ; Matrix multiplication ; Matrix transposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we introduce parallel versions of two hierarchical memory models and give optimal algorithms in these models for sorting, FFT, and matrix multiplication. In our parallel models, there areP memory hierarchies operating simultaneously; communication among the hierarchies takes place at a base memory level. Our optimal sorting algorithm is randomized and is based upon the probabilistic partitioning technique developed in the companion paper for optimal disk sorting in a two-level memory with parallel block transfer. The probability of using/times the optimal running time is exponentially small in ι(log ι) logP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185208
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    The uniform memory hierarchy model of computation (1994)
    Springer
    Algorithmica 12 (1994), S. 72-109 
    Details
    ISSN: 1432-0541
    Keywords: Memory hierarchy ; Model of computation ; FFT ; Matrix multiplication ; High-performance computing ; Performance programming ; Cache architecture ; Bridging model
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract TheUniform Memory Hierarchy (UMH) model introduced in this paper captures performance-relevant aspects of the hierarchical nature of computer memory. It is used to quantify architectural requirements of several algorithms and to ratify the faster speeds achieved by tuned implementations that use improved data-movement strategies. A sequential computer's memory is modeled as a sequence 〈M 0,M 1,...〉 of increasingly large memory modules. Computation takes place inM 0. Thus,M 0 might model a computer's central processor, whileM 1 might be cache memory,M 2 main memory, and so on. For each moduleM u, a busB u connects it with the next larger module Mu+1. All buses may be active simultaneously. Data is transferred along a bus in fixed-sized blocks. The size of these blocks, the time required to transfer a block, and the number of blocks that fit in a module are larger for modules farther from the processor. The UMH model is parametrized by the rate at which the blocksizes increase and by the ratio of the blockcount to the blocksize. A third parameter, the transfer-cost (inverse bandwidth) function, determines the time to transfer blocks at the different levels of the hierarchy. UMH analysis refines traditional methods of algorithm analysis by including the cost of data movement throughout the memory hierarchy. Thecommunication efficiency of a program is a ratio measuring the portion of UMH running time during which M0 is active. An algorithm that can be implemented by a program whose communication efficiency is nonzero in the limit is said to becommunication- efficient. The communication efficiency of a program depends on the parameters of the UMH model, most importantly on the transfer-cost function. Athreshold function separates those transfer-cost functions for which an algorithm is communication-efficient from those that are too costly. Threshold functions for matrix transpose, standard matrix multiplication, and Fast Fourier Transform algorithms are established by exhibiting communication-efficient programs at the threshold and showing that more expensive transfer-cost functions are too costly. A parallel computer can be modeled as a tree of memory modules with computation occurring at the leaves. Threshold functions are established for multiplication ofN×N matrices using up to N2 processors in a tree with constant branching factor.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185206
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    Algorithms for parallel memory, I: Two-level memories (1994)
    Springer
    Algorithmica 12 (1994), S. 110-147 
    Details
    ISSN: 1432-0541
    Keywords: I/O, Input/output ; Disk ; Secondary memory ; Sorting ; Distribution sort ; FFT ; Matrix multiplication ; Transposition ; Permutation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems. Our two-level memory model is new and gives a realistic treatmentof parallel block transfer, in which during a single I/O each of theP secondary storage devices can simultaneously transfer a contiguous block ofB records. The model pertains to a large-scale uniprocessor system or parallel multiprocessor system withP disks. In addition, the sorting, FFT, permutation network, and standard matrix multiplication algorithms are typically optimal in terms of the amount of internal processing time. The difficulty in developing optimal algorithms is to cope with the partitioning of memory intoP separate physical devices. Our algorithms' performances can be significantly better than those obtained by the wellknown but nonoptimal technique of disk striping. Our optimal sorting algorithm is randomized, but practical; the probability of using more than ι times the optimal number of I/Os is exponentially small inl(logl) log(M/B), whereM is the internal memory size.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185207
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Locality-preserving hash functions for general purpose parallel computation (1994)
    Springer
    Algorithmica 12 (1994), S. 170-181 
    Details
    ISSN: 1432-0541
    Keywords: General-purpose parallel computation ; Communication latency ; Block PRAM ; Locality ; PRAM simulations ; Universal hashing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider the problem of efficiently simulating the shared-memory parallel random access machine (PRAM) model on massively parallel architectures with physically distributed memory. To prevent network congestion and memory bank contention, it may be advantageous to hash the shared memory address space. The decision on whether or not to use hashing depends on (1) the communication latency in the network and (2) the locality of memory accesses in the algorithm. We relate this decision directly to algorithmic issues by studying the complexity of hashing in the Block PRAM model of Aggarwal, Chandra, and Snir, a shared-memory model of parallel computation which accounts for communication locality. For this model, we exhibit a universal family of hash functions having optimal locality. The complexity of applying these hash functions to the shared address space of the Block PRAM (i.e., by permuting data elements) is asymptotically equivalent to the complexity of performing a square matrix transpose, and this result is best possible for all pairwise independent universal hash families. These complexity bounds provide theoretical evidence that hashing and randomized routing need not destroy communication locality, addressing an open question of Valiant.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185209
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    Guest editor's foreword special issue on string algorithmics and its applications (1994)
    Springer
    Algorithmica 12 (1994), S. 245-246 
    Details
    ISSN: 1432-0541
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185426
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    String layouts for a redundant array of inexpensive disks (1994)
    Springer
    Algorithmica 12 (1994), S. 209-224 
    Details
    ISSN: 1432-0541
    Keywords: RAID ; Disk array ; 2d-Parity ; Fault tolerance ; Disk strings ; Bad square
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This article introduces the concept of abad square in aredundant array of inexpensive disks (RAID). Bad squares are used to prove upper limits on the reliability of the2d-parity arrangement when there is the possibility that astring of disks may fail simultaneously. Bad-square analysis motivates several optimal string layouts which achieve these limits. Bad squares also provide a means to calculate the mean time to data loss for a RAID layout, without the use of Monte Carlo simulation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185211
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    Coding techniques for handling failures in large disk arrays (1994)
    Springer
    Algorithmica 12 (1994), S. 182-208 
    Details
    ISSN: 1432-0541
    Keywords: Input/output architecture ; Redundant disk arrays ; RAID ; Error-correcting codes ; Reliability ; Availability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A crucial issue in the design of very large disk arrays is the protection of data against catastrophic disk failures. Although today single disks are highly reliable, when a disk array consists of 100 or 1000 disks, the probability that at least one disk will fail within a day or a week is high. In this paper we address the problem of designing erasure-correcting binary linear codes that protect against the loss of data caused by disk failures in large disk arrays. We describe how such codes can be used to encode data in disk arrays, and give a simple method for data reconstruction. We discuss important reliability and performance constraints of these codes, and show how these constraints relate to properties of the parity check matrices of the codes. In so doing, we transform code design problems into combinatorial problems. Using this combinatorial framework, we present codes and prove they are optimal with respect to various reliability and performance constraints.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185210
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    Checking the correctness of memories (1994)
    Springer
    Algorithmica 12 (1994), S. 225-244 
    Details
    ISSN: 1432-0541
    Keywords: Program checking ; Hashing ; Stack ; Queue ; RAM ; Data structure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We extend the notion of program checking to include programs which alter their environment. In particular, we consider programs which store and retrieve data from memory. The model we consider allows the checker a small amount of reliable memory. The checker is presented with a sequence of requests (on-line) to a data structure which must reside in a large but unreliable memory. We view the data structure as being controlled by an adversary. We want the checker to perform each operation in the input sequence using its reliable memory and the unreliable data structure so that any error in the operation of the structure will be detected by the checker with high probability. We present checkers for various data structures. We prove lower bounds of logn on the amount of reliable memory needed by these checkers wheren is the size of the structure. The lower bounds are information theoretic and apply under various assumptions. We also show time-space tradeoffs for checking random access memories as a generalization of those for coherent functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185212
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    On Boyer-Moore automata (1994)
    Springer
    Algorithmica 12 (1994), S. 268-292 
    Details
    ISSN: 1432-0541
    Keywords: String searching ; Pattern matching ; Finite automaton ; Average-case analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The notion of Boyer-Moore automaton was introduced by Knuth, Morris, and Pratt in their historical paper on fast pattern matching. It leads to an algorithm that requires more preprocessing but is more efficient than the original Boyer-Moore's algorithm. We formalize the notion of Boyer-Moore automaton and we give an efficient building algorithm. Also, bounds on the number of states are presented, and the concept of potential of a transition is introduced to improve the worst-and average-case behavior of these machines. We show that looking at the rightmost unknown character, as suggested by Knuthet al., is not necessarily optimal.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185428
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Performance analysis of some simple heuristics for computing longest common subsequences (1994)
    Springer
    Algorithmica 12 (1994), S. 293-311 
    Details
    ISSN: 1432-0541
    Keywords: Longest common subsequence ; Heuristics ; Performance analysis ; Scan algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Although theLongest Common Subsequence (LCS)Problem has been studied by many researchers for years, heuristic methods have not been investigated before. In this paper we present a simple heuristic which guarantees to return a common subsequence of length at least 1/s that of the longest wheres is the number of different symbols in the input strings. Furthermore, we generalize the idea to several classes of heuristic algorithms. Surprisingly, we find that no other heuristic in these classes outperforms this simple algorithm. In other words, we show that any heuristic which uses only global information, such as number of symbol occurrences, might return a common subsequence as short as 1/s of the length of the longest. Analysis of the average performance of the simple heuristic fors=2 is also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185429
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    Speeding up two string-matching algorithms (1994)
    Springer
    Algorithmica 12 (1994), S. 247-267 
    Details
    ISSN: 1432-0541
    Keywords: Analysis of algorithms ; Pattern matching ; String matching ; Suffix tree ; Suffix automaton ; Combinatorial problems ; Periods ; Text processing ; Data retrieval
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show how to speed up two string-matching algorithms: the Boyer-Moore algorithm (BM algorithm), and its version called here the reverse factor algorithm (RF algorithm). The RF algorithm is based on factor graphs for the reverse of the pattern. The main feature of both algorithms is that they scan the text right-to-left from the supposed right position of the pattern. The BM algorithm goes as far as the scanned segment (factor) is a suffix of the pattern. The RF algorithm scans while the segment is a factor of the pattern. Both algorithms make a shift of the pattern, forget the history, and start again. The RF algorithm usually makes bigger shifts than BM, but is quadratic in the worst case. We show that it is enough to remember the last matched segment (represented by two pointers to the text) to speed up the RF algorithm considerably (to make a linear number of inspections of text symbols, with small coefficient), and to speed up the BM algorithm (to make at most 2 ·n comparisons). Only a constant additional memory is needed for the search phase. We give alternative versions of an accelerated RF algorithm: the first one is based on combinatorial properties of primitive words, and the other two use the power of suffix trees extensively. The paper demonstrates the techniques to transform algorithms, and also shows interesting new applications of data structures representing all subwords of the pattern in compact form.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185427
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Parametric optimization of sequence alignment (1994)
    Springer
    Algorithmica 12 (1994), S. 312-326 
    Details
    ISSN: 1432-0541
    Keywords: Sequence alignment ; Parametric analysis ; Edit distance ; Sequence homology ; Global alignment ; Local alignment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Theoptimal alignment or theweighted minimum edit distance between two DNA or amino acid sequences for a given set of weights is computed by classical dynamic programming techniques, and is widely used in molecular biology. However, in DNA and amino acid sequences there is considerable disagreement about how to weight matches, mismatches, insertions/deletions (indels or spaces), and gaps.Parametric sequence alignment is the problem of computing the optimal-valued alignment between two sequences as afunction of variable weights for matches, mismatches, spaces, and gaps. The goal is to partition the parameter space into regions (which are necessarily convex) such that in each region one alignment is optimal throughout and such that the regions are maximal for this property. In this paper we are primarily concerned with the structure of this convex decomposition, and secondarily with the complexity of computing the decomposition. The most striking results are the following: For the special case where only matches, mismatches, and spaces are counted, and where spaces are counted throughout the alignment, we show that the decomposition is surprisingly simple: all regions are infinite; there are at most n2/3 regions; the lines that bound the regions are all of the form Β=c + (c + 0.5)α; and the entire decomposition can be found inO(knm) time, wherek is the actual number of regions, andn〈m are the lengths of the two strings. These results were found while implementing a large software package for parametric sequence analysis, and in turn have led to faster algorithms for those tasks. A conference version of this paper first appeared in [10].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185430
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors (1994)
    Springer
    Algorithmica 12 (1994), S. 421-435 
    Details
    ISSN: 1432-0541
    Keywords: Spanning tree ; Steiner tree ; Heuristic algorithm ; Computational geometry ; Rectilinear distance ; Nearest neighbor ; Geographic nearest neighbor ; Decomposable search problem ; Range tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n 2 log n) toO(n log2 n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188713
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    Polynomial algorithms for linear programming over the algebraic numbers (1994)
    Springer
    Algorithmica 12 (1994), S. 436-457 
    Details
    ISSN: 1432-0541
    Keywords: Linear programming ; Algebraic numbers ; Computational complexity ; Ellipsoid method ; Polynomial-time algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We derive a bound on the computational complexity of linear programs whose coefficients are real algebraic numbers. Key to this result is a notion of problem size that is analogous in function to the binary size of a rational-number problem. We also view the coefficients of a linear program as members of a finite algebraic extension of the rational numbers. The degree of this extension is an upper bound on the degree of any algebraic number that can occur during the course of the algorithm, and in this sense can be viewed as a supplementary measure of problem dimension. Working under an arithmetic model of computation, and making use of a tool for obtaining upper and lower bounds on polynomial functions of algebraic numbers, we derive an algorithm based on the ellipsoid method that runs in time bounded by a polynomial in the dimension, degree, and size of the linear program. Similar results hold under a rational number model of computation, given a suitable binary encoding of the problem input.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188714
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    New results for the minimum weight triangulation problem (1994)
    Springer
    Algorithmica 12 (1994), S. 533-552 
    Details
    ISSN: 1432-0541
    Keywords: Minimum weight triangulation ; Greedy triangulation ; Delaunay triangulation ; Minimum spanning tree ; NP-Hardness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is known to find a triangulation of minimum weight, nor is the minimum weight triangulation problem known to be NP-hard. This paper proposes a new heuristic algorithm that triangulates a set ofn points inO(n 3) time and that never produces a triangulation whose weight is greater than that of a greedy triangulation. The algorithm produces an optimal triangulation if the points are the vertices of a convex polygon. Experimental results indicate that this algorithm rarely produces a nonoptimal triangulation and performs much better than a seemingly similar heuristic of Lingas. In the direction of showing the minimum weight triangulation problem is NP-hard, two generalizations that are quite close to the minimum weight triangulation problem are shown to be NP-hard.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188718
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    Thek-server dual and loose competitiveness for paging (1994)
    Springer
    Algorithmica 11 (1994), S. 525-541 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; k-Server problem ; Linear programming ; Approximation algorithms ; Paging ; Caching ; Competitive analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Weighted caching is a generalization ofpaging in which the cost to evict an item depends on the item. We study both of these problems as restrictions of the well-knownk-server problem, which involves moving servers in a graph in response to requests so as to minimize the distance traveled. We give a deterministic on-line strategy for weighted caching that, on any sequence of requests, given a cache holdingk items, incurs a cost within a factor ofk/(k−h+1) of the minimum cost possible given a cache holdingh items. The strategy generalizes “least recently used,” one of the best paging strategies in practice. The analysis is a primal-dual analysis, the first for an on-line problem, exploiting the linear programming structure of thek-server problem. We introduceloose competitiveness, motivated by Sleator and Tarjan's complaint [ST] that the standard competitive ratios for paging strategies are too high. Ak-server strategy isloosely c(k)-competitive if, for any sequence, foralmost all k, the cost incurred by the strategy withk serverseither is no more thanc(k) times the minimum costor is insignificant. We show that certain paging strategies (including “least recently used,” and “first in first out”) that arek-competitive in the standard model are looselyc(k)-competitive providedc(k)/Ink→∞ and bothk/c(k) andc(k) are nondecreasing. We show that the marking algorithm, a randomized paging strategy that is Θ(Ink)-competitive in the standard model, is looselyc(k)-competitive providedk−2 In Ink→∞ and both 2 Ink−c(k) andc(k) are nondecreasing.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189992
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    Sublinear approximate string matching and biological applications (1994)
    Springer
    Algorithmica 12 (1994), S. 327-344 
    Details
    ISSN: 1432-0541
    Keywords: Pattern matching ; Edit distance ; Suffix tree ; Lowest common ancestor ; Chernoff bound ; Computational biology
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a text string of lengthn and a pattern string of lengthm over ab-letter alphabet, thek differences approximate string matching problem asks for all locations in the text where the pattern occurs with at mostk differences (substitutions, insertions, deletions). We treatk not as a constant but as a fraction ofm (not necessarily constant-fraction). Previous algorithms require at leastO(kn) time (or exponential space). We give an algorithm that is sublinear time0((n/m)k log b m) when the text is random andk is bounded by the threshold m/(logb m + O(1)). In particular, whenk=o(m/logb m) the expected running time iso(n). In the worst case our algorithm is O(kn), but is still an improvement in that it is practical and uses0(m) space compared with0(n) or0(m 2). We define three problems motivated by molecular biology and describe efficient algorithms based on our techniques: (1) approximate substring matching, (2) approximate-overlap detection, and (3) approximate codon matching. Respectively, applications to biology are local similarity search, sequence assembly, and DNA-protein matching.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185431
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    A sublinear algorithm for approximate keyword searching (1994)
    Springer
    Algorithmica 12 (1994), S. 345-374 
    Details
    ISSN: 1432-0541
    Keywords: Approximate match ; Dynamic programming ; Index ; word neighborhood
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a relatively short query stringW of lengthP, a long subject stringA of lengthN, and a thresholdD, theapproximate keyword search problem is to find all substrings ofA that align withW with not more than D insertions, deletions, and mismatches. In typical applications, such as searching a DNA sequence database, the size of the “database”A is much larger than that of the queryW, e.g.,N is on the order of millions or billions andP is a hundred to a thousand. In this paper we present an algorithm that given a precomputedindex of the databaseA, finds rare matches in time that issublinear inN, i.e.,N c for somec〈1. The sequenceA must be overa. finite alphabet σ. More precisely, our algorithm requires 0(DN pow(ɛ) logN) expected-time where ɛ=D/P is the maximum number of differences as a percentage of query length, and pow(ɛ) is an increasing and concave function that is 0 when ɛ=0. Thus the algorithm is superior to current O(DN) algorithms when ɛ is small enough to guarantee that pow(ɛ) 〈 1. As seen in the paper, this is true for a wide range of ɛ, e.g., ɛ. up to 33% for DNA sequences (¦⌆¦=4) and 56% for proteins sequences (¦⌆¦=20). In preliminary practical experiments, the approach gives a 50-to 500-fold improvement over previous algorithms for prolems of interest in molecular biology.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185432
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    Pattern matching in a digitized image (1994)
    Springer
    Algorithmica 12 (1994), S. 375-408 
    Details
    ISSN: 1432-0541
    Keywords: Digitization ; Efficient algorithms ; Image processing ; String matching
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract For motivation purpose, imagine the followingcontinuous pattern-matching problem. Two continuous pictures, each consisting of unicolor regions, are given; one picture is called thescene and the other thepattern. The problem is to find all occurrences of the pattern in the scene. As a step toward efficient algorithmic handling of the continuous pattern-matching problem by computers, where discretized representations are involved, we consider pattern-matching problems where the pattern and the text are specified either in terms of the “continuous” properties, or through other exemplar digitized images—a variety of alternative specifications is considered. From the perspective of areas such as computer vision or image processing, our problem definitions identify an important gap in the fundamental theory of image formation and image processing—how to determine, even in the absence of noise, if a digitized image of a scene could contain an image of a given pattern. This is done using carefulaxiomatization. Such a “digitized-based” approach may lead toward building on the theory of string-matching algorithms (in one, or higher, dimensions) for the benefit of algorithmic pattern matching in image processing.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185433
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    Complexity aspects of guessing prefix codes (1994)
    Springer
    Algorithmica 12 (1994), S. 409-419 
    Details
    ISSN: 1432-0541
    Keywords: Prefix codes ; Huffman codes ; Encryption ; Complexity ; NP-completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a natural language cleartext and a ciphertext obtained by Huffman coding, the problem of guessing the code is shown to be NP-complete for various variants of the encoding process.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185434
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    External segment trees (1994)
    Springer
    Algorithmica 12 (1994), S. 498-532 
    Details
    ISSN: 1432-0541
    Keywords: Segment tree ; Intervals ; Point enclosure search ; Spatial search ; Temporal databases ; File structures ; Tree balancing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The segment tree is a well-known internal data structure with numerous applications in computational geometry. It allows the dynamical maintenance of a set of intervals such that the intervals enclosing a query point can be found efficiently (point enclosure search). In this paper we transfer the underlying principle of the segment tree in a nontrivial way to secondary storage and arrive at the EST-an external file structure with the same functionality and the following properties: (1) Point enclosure searches are very efficient—only very few pages are accessed that are not filled to more than 50% with result intervals. (2) A page filling of 50% is guaranteed—on the average it will be around 70%. Although the segment tree represents, in the worst case, each interval by a logarithmic number offragments, in practical cases fragmentation remains low and the storage requirements about linear. (3) The EST is balanced and the update algorithms are efficient. (4) Unlike many other file structures for spatial objects the EST has no problems with an arbitrarydensity, that is, an arbitrarily large number of intervals covering any point of the line. Furthermore, the EST can be used as a file structureconstructor in the following sense: Let there be a file structureX supporting searches for objects with propertyx and suppose it is necessary to maintain a collection of objects with associated (e.g., time) intervals. Then an EST-X structure that supports searches for objects with propertyx present at timet can be built. This suggests using the EST as a building block in the implementation of temporal database systems. Other applications include the one-dimensional indexing of collections of spatial objects in two or more dimensions. More generally, this paper shows techniques for mapping internal tree structures with node lists (other examples: range tree, interval tree) to secondary memory. In this context an intriguing theoretical problem, thecover-balancing problem, is solved: Given a tree whose nodes have associatedweights partitioned into subtrees whose weights must lie in a certain range, maintain this partition under weight changes at arbitrary nodes. This is in contrast to classical balancing problems where updates occur only at the leaves.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188717
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    Heuristic sampling on DAGs (1994)
    Springer
    Algorithmica 12 (1994), S. 458-475 
    Details
    ISSN: 1432-0541
    Keywords: Heuristics ; Sampling ; Cost prediction ; Monte-Carlo method ; Analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In theory, many problems in computer applications can be solved by searching through a directed-acyclic graph (DAG). In practice, however, this approach has been hampered by our analytical inability to predict the search cost accurately without actually implementing and executing the program. To overcome this inability, a simple and quick heuristic procedure based on a stratified sampling approach is presented. It generalizes a tree sampling technique already shown to be useful in predicting the performance of tree-searching programs. With the addition of this DAG sampling procedure, we should be able to forecast the complexity and feasibility of alternative tree or DAG searching algorithms so that we may utilize our computational resources more effectively.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188715
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    Upward drawings of triconnected digraphs (1994)
    Springer
    Algorithmica 12 (1994), S. 476-497 
    Details
    ISSN: 1432-0541
    Keywords: Planarity ; Automatic graph drkwing ; Hierarchical structures ; Max-flow ; st-Digraphs ; Acyclic digraphs ; Ordered sets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A polynomial-time algorithm for testing if a triconnected directed graph has an upward drkwing is presented. An upward drkwing is a planar drkwing such that all the edges flow in a common direction (e.g., from bottom to top). The problem arises in the fields of automatic graph drkwing and ordered sets, and has been open for several years. The proposed algorithm is based on a new combinatorial characterization that maps the problem into a max-flow problem on a sparse network; the time complexity isO(n+r 2) , wheren is the number of vertices andr is the number of sources and sinks of the directed graph. If the directed graph has an upward drkwing, the algorithm allows us to construct one easily.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188716
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Guest editor's foreword (1994)
    Springer
    Algorithmica 11 (1994), S. 1-1 
    Details
    ISSN: 1432-0541
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294259
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    PDL-HM: morphological and syntactic shape classification algorithm (1994)
    Springer
    Machine vision and applications 7 (1994), S. 59-68 
    Details
    ISSN: 1432-1769
    Keywords: Industrial machine vision ; Real-time processing ; Image morphology ; Hit- and-miss transform ; Picture description language ; Neural networks ; Shape classification ; Fish processing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper describes a novel shape classification technique in computer vision called PDL-HM, which combines the selection of morphological structuring elements from contour description languages, the extraction of shape characteristics by the hit- and-miss transform, and shape classification by a neural network. This real-time method is orientation independent and tolerates limited object overlap. It is illustrated by an application to fish species classification in an industrial enviromnent and performs excellently
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215802
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    An optimization algorithm for shape analysis of regular polygons (1994)
    Springer
    Machine vision and applications 7 (1994), S. 82-92 
    Details
    ISSN: 1432-1769
    Keywords: Optimization ; Least-squares fitting ; Modelbased inspection ; Vision systems ; Regular polygons
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Machine vision has the potential to impact both quality and productivity significantly in computer integrated manufacturing due to its versatility, flexibility, and relative speed. Unfortunately, algorithm development has not kept pace with the advances in vision-hardware technology, particularly in the areas of analysis and decision making. The specific subject of this investigation is the development of a machine-vision algorithm for the dimensional checking, pose estimation, and overall shape verification of regular polygonal objects (e.g., surface-mounted electronic components and fastener heads). Algorithmically, the image boundary data is partitioned inton segments, and then a non-ordinary least squares technique is used to find the best fitting polygon. The algorithm is well-suited for online implementation in an automated environment due to its flexibility and demonstrated speed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215804
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    Optimal template matching by nonorthogonal image expansion using restoration (1994)
    Springer
    Machine vision and applications 7 (1994), S. 69-81 
    Details
    ISSN: 1432-1769
    Keywords: Template matching ; Expansion matching ; Nonorthogonal expansion ; Correlation matching ; Matched filtering ; Restoration ; Discriminative signal-to-noise ratio (DSNR)
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we present a novel approach for template matching. The basic principle is expansion matching and it entails signal expansion into a set of nonorthogonal templatesimilar basis functions. The coefficients of this expansion signify the presence of the template in the corresponding locations in the image. We demonstrate that this matching technique is robust in conditions of noise, superposition, and severe occlusion. A new and more practical discriminative signal-to-noise ratio (DSNR) for matching is proposed that considers even the filter's off-center response to the template as “noise”. We show that expansion yields the optimal linear operator that maximizes the DSNR and results in a sharp response to the matched template. Theoretical and experimental comparisons of expansion matching and the widely used correlation matching demonstrate the superiority of our approach. Correlation matching (also known as matched filtering) yields broad peaks and spurious responses, both of which hamper good detection. We also show that the special case of expansion with a dense set of self-similar basis functions is equivalent to signal restoration. Expansion matching can be implemented by restoration techniques and also by our recently developed lattice architecture.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215803
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    Error propagation in machine vision (1994)
    Springer
    Machine vision and applications 7 (1994), S. 93-114 
    Details
    ISSN: 1432-1769
    Keywords: Error propagation ; Measurement ; Edge perturbation ; Noise ; Inspection ; Analysis of variance
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Machine vision systems that perform inspection tasks must be capable of making measurements. A vision system measures an image to determine a measurement of the object being viewed. The image measurement depends on several factors, including sensing, image processing, and feature extraction. We consider the error that can occur in measuring the distance between two corner points of the 2D image. We analyze the propagation of the uncertainty in edge point position to the 2D measurements made by the vision system, from 2D curve extraction, through point determination, to measurement. We extend earlier work on the relationship between random perturbation of edge point position and variance of the least squares estimate of line parameters and analyze the relationship between the variance of 2D points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215805
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    Fast segmentation of range images into planar regions by scan line grouping (1994)
    Springer
    Machine vision and applications 7 (1994), S. 115-122 
    Details
    ISSN: 1432-1769
    Keywords: Algorithm ; Range data ; Segmentation ; Region growing ; Planar surfaces
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A novel technique is presented for rapid partitioning of surfaces in range images into planar patches. The method extends and improves Pavlidis' algorithm (1976), proposed for segmenting images from electron microscopes. The new method is based on region growing where the segmentation primitives are scan line grouping features instead of individual pixels. We use a noise variance estimation to automatically set thresholds so that the algorithm can adapt to the noise conditions of different range images. The proposed algorithm has been tested on real range images acquired by two different range sensors. Experimental results show that the proposed algorithm is fast and robust.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215806
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    About the authors (1994)
    Springer
    Machine vision and applications 7 (1994), S. 124-124 
    Details
    ISSN: 1432-1769
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215808
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    Dissertation abstracts (1994)
    Springer
    Machine vision and applications 7 (1994), S. 123-123 
    Details
    ISSN: 1432-1769
    Keywords: Image processing ; ANOVA ; Frame segmentation ; Graeco-Latin squares ; Object motion ; Edge detection ; ANOVA ; MIPT ; Image processing ; Partition tests ; Step, slant, roof and odd symmetric edge detection ; ANOVA ; ANCOVA ; Connectivity and colinearity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215807
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    Call for papers (1994)
    Springer
    Machine vision and applications 7 (1994), S. A9 
    Details
    ISSN: 1432-1769
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01215809
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Introduction (1994)
    Springer
    Machine vision and applications 7 (1994), S. 125-126 
    Details
    ISSN: 1432-1769
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211657
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Autonomous landing of airplanes by dynamic machine vision (1994)
    Springer
    Machine vision and applications 7 (1994), S. 127-134 
    Details
    ISSN: 1432-1769
    Keywords: Autonomous landing ; Vision-based control ; Extended Kalman filter ; Flight guidance ; Multipoint aircraft model
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The 4D approach to dynamic machine vision has been validated for the application area of on-board autonomous landing approaches in the visual flight regime with computing technology available today; sensors are a video-camera, inertial gyros and an air velocity meter. The key feature of the method is the reconstruction and servo-maintained adjustment by prediction error feedback of an internal spatiotemporal model about the process to be controlled. This encompasses both the egomotion state of the aircraft carrying the sensors and the relevant geometric properties of the runway and its spatial environment. The efficiency of the approach is proved both in a hardware-in-the-loop simulation and in real test flights with a twin turbo-prop aircraft. For accuracy evaluation of the data gathered, the results of differential GPS and radiometric altitude measurements have been recorded simultaneously.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211658
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    A knowledge-based image-inspection system for automatic defect recognition, classification, and process diagnosis (1994)
    Springer
    Machine vision and applications 7 (1994), S. 135-147 
    Details
    ISSN: 1432-1769
    Keywords: Image inspection ; Defect classification and diagnosis ; Knowledge-based image-inspection system ; Data-driven approach ; Knowledge acquisition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Combining knowledge-based processing with image processing is a key issue in the future of the visual inspection of complex patterns such as offset prints. Often the class of the defect determines the state of the process, which must known for eliminating the cause of the defect. We describe the architecture of such a complex knowledge-based inspection system. The system has been used for defect recognition and misprint diagnosis in offset printing, but it is flexible enough for other applications. The system is based on a set of general and powerful tools for the knowledge interpretation of sensor signals. An object-oriented concept and task-dependent algorithms for efficient image processing are implemented. The paper concentrates on four points: integration of the system in the offset printing process, a description of the system architecture, knowledge acquisition, and implementation results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211659
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    An image analysis system for automatic data acquisition from colored scanned maps (1994)
    Springer
    Machine vision and applications 7 (1994), S. 148-164 
    Details
    ISSN: 1432-1769
    Keywords: Map interpretation ; Topographic maps ; Color scanning ; Raster image analysis ; Knowledge-directed interpretation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Many maps [an important source of information for efficient spatial data evaluation using a Geographic Information System (GIS)] must still be digitized manually, a time-consuming and error-prone process. Therefore, we developed the processing of maps (PROMAP) system, which incorporates adequate image analysis. The system can generate a symbolic description of the map that can be imported into a GIS. A color scanner generates a multicolor raster image of the map. This image is split into layers of predefined map colors. Each layer is vectorized and methods like neural network-based symbol and object recognition for the extraction of attributed structure primitives and knowledge-directed image interpretation are applied. The map scene is structured hierarchically. The interface to the GIS is represented by the map objects at the upper levels of hierarchy. These investigations described are part of the interdisciplinary projectEnvironmental Planning System. The scope of this project is the combination of data acquisition, the development of an evaluation scheme, and GIS in an integrated concept.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211660
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    Road obstacle detection and tracking by an active and intelligent sensing strategy (1994)
    Springer
    Machine vision and applications 7 (1994), S. 165-177 
    Details
    ISSN: 1432-1769
    Keywords: Active and intelligent sensing ; Visual target ; Road obstacle ; Fusion ; Tracking
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper, we address the problem of road obstacle deletion. We propose a method based on an active and intelligent sensing strategy. A sensor composed of a range finder coupled with a (charge-coupled-device) CCD camera is used. This sensor is mounted in front of a vehicle. The basic idea is first to determine 2D visual targets in intensity images of the camera. Then the range finder will be used not only to confirm or reject the existence of the detected visual targets, but also to acquire 3D information of the confirmed visual targets. The central problem of this strategy is how to detect 2D visual targets from intensity images of a road scene. In our method, we consider line segments as significant features. We use the concept ofline segment of interest and the concept ofdominant line segment. With the help of the identified dominant line segments in an image, we can effectively ascertain 2D visual targets. Finally, we use the range finder to confirm or reject a 2D visual target. A confirmed visual target is temporally tracked with the help of the range finder.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211661
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Patterned wafer inspection by high resolution spectral estimation techniques (1994)
    Springer
    Machine vision and applications 7 (1994), S. 178-185 
    Details
    ISSN: 1432-1769
    Keywords: Defect detection ; Wafer inspection ; Spectral estimation ; Microlithography ; IC manufacturing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A new self-reference signal processing technique is proposed for detecting the location of irregularities and defects in a periodic two-dimensional signal or image. Using high-resolution spectral estimation algorithms, the proposed technique first extracts the period and structure of repeated patterns from the image. Then a defect-free reference image for comparison with the actual image is produced. Since the technique acquires all the information needed from a single image (in contrast to most existing methods), there is no need for a database image, a scaling or alignment procedure or any a priori knowledge about the repetition period of the patterns. Potential application fields for the proposed method range from the area of wafer and mask defect inspection, which includes inspection of memory chips, shift registers, switched capacitors, CCD arrays, and LCD displays to other areas that deal with repeated structures, such as crystallography. Some results of applying the proposed technique to real images from microlithography are presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211662
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Estimation of motion vectors and their application to scene retrieval (1994)
    Springer
    Machine vision and applications 7 (1994), S. 199-208 
    Details
    ISSN: 1432-1769
    Keywords: Motion estimation ; Similarity retrieval ; Multimedia database
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper describes a method for retrieving scenes from a motion picture database by using motion information as a key. The method has three steps: the automatic estimation of motion vectors in frame sequences, the description of motions in spatio-temporal space, and the retrieval of sequences of images. The motion vectors are estimated by block matching. Estimated motion vectors are mapped in spatio-temporal space (x, y, t). Motion vectors in a scene are aggregated into several representative vectors by statistical analysis. The retrieval of scenes is divided into two parts: the specification of query conditions, and matching between the query conditions and the motion database. Similarity is defined in spatio-temporal space as the distance between the query conditions and the stored motion index. Candidate scenes are ranked in order of distance. Experimental results indicate that the proposed method is effective.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211664
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    About the author (1994)
    Springer
    Machine vision and applications 7 (1994), S. 217-218 
    Details
    ISSN: 1432-1769
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211666
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    A high-quality 3D multiview model-building technique based on CAD (1994)
    Springer
    Machine vision and applications 7 (1994), S. 209-216 
    Details
    ISSN: 1432-1769
    Keywords: 3D object representation and recognition ; CAD-based vision ; 3D multiview model ; Image-precision method ; Object-precision method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper, we propose a method for building a high-quality 3D model efficiently from a CAD model. We automatically build the high-quality 3D model of an object by accurately extracting the 3D multiview features from the CAD model with the object-precision method instead of the existing image-precision method. Precision of the features from the image-precision method is limited to the precision of the image resolution and varies with the view distance and view-up vector. Since we exploit the object-precision method to extract the 3D multiview features, the precision of the features is equal to the precision at which the object is defined in the CAD and is independent of the view distance and view-up vector.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211665
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    A machine vision system for enhancing the teleoperation of an industrial robot (1994)
    Springer
    Machine vision and applications 7 (1994), S. 187-198 
    Details
    ISSN: 1432-1769
    Keywords: Motion computation ; Tracking ; Self-localization ; Image processing ; Navigation ; Camera calibration
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper describes a real-time vision system that enhances the teleoperation of a servicing tool used in the heat exchangers of nuclear power plants. The vision system is used to track the position of the tool as it moves over a sheet of tube ends. A map-based strategy is adopted for the estimation of the position. The system incorporates a novel method for a foreshortening correction that is applied prior to map referencing. A hypothesize and verify scheme locates two image features that correspond to two map features. An efficient scheme for extracting image features is developed to locate these two features (tube-end centers) in the image. Two different types of heat-exchanger tube sheets are accounted for. They are those with tube ends placed in a square grid and those with tube ends placed in a triangular grid. The map-based strategy minimizes the cumulative errors in the estimate of the tool head position. The resulting low-cost system has been tested on synthetic and real data. Performance results are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211663
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Call for papers (1994)
    Springer
    Machine vision and applications 7 (1994), S. A5 
    Details
    ISSN: 1432-1769
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01211667
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    Special section on frontiers in machine vision applications introduction (1994)
    Springer
    Machine vision and applications 7 (1994), S. 219-219 
    Details
    ISSN: 1432-1769
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01213411
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    A real-time vision system using an integrated memory array processor prototype (1994)
    Springer
    Machine vision and applications 7 (1994), S. 220-228 
    Details
    ISSN: 1432-1769
    Keywords: SIMD ; Parallel processing ; Image processing ; Real-time vision
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper describes a real-time vision system (RVS) architecture and performance and its use of an integrated memory array processor (IMAP) prototype. This prototype integrates eight 8-bit processors and a 144-kbit SRAM on a single chip. The RVS was developed with 64 IMAP prototypes connected in series in a 512 processor-system configuration. A host workstation can access the memory on the IMAP prototypes directly through a random access port. Images are inputted and outputted at high speed through serial access ports. The RVS performance is shown in real-time road-image processing and in a neural network simulation, as well as in low-level image processing algorithms, such as filtering, histograms, discrete cosine transform (DCT), and rotation. The RVS image processing is shown to be much faster than the video rate.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01213412
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    A multiscale regularity measure as a geometric criterion for image segmentation (1994)
    Springer
    Machine vision and applications 7 (1994), S. 229-236 
    Details
    ISSN: 1432-1769
    Keywords: Image segmentation ; Fractal dimension ; Region growing ; Regularity measure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Recent results from human vision experiments show that lines of low fractal dimension are highly capable of evoking indification with nameable objects. In other words, regular lines are recognized in human vision as object edges. In this paper, a regularity measure of discrete line geometry is presented. This quantitative measure based on a ratio between lines of varying lengths is analyzed in the framework of brownian motion theory. The measure on a given scale is always computed from the maximum precision image, so that no subresolution assumption is introduced. A choice of scale determines the quantity of global information versus local information one wants to measure. We show how this quantitative measure leads to relevant shape information. To illustrate this, an example of an image segmentation application is realized. The segmentation based essentially on geometry criteria, uses a region-growing process. The process depends on a single parameter that can be fixed in a natural way, comparing contour regularity to a geometric model regularity. We present experimental results performed on real-scene images, including indoor and outdoor images.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01213413
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    Layout extraction of mixed mode documents (1994)
    Springer
    Machine vision and applications 7 (1994), S. 237-246 
    Details
    ISSN: 1432-1769
    Keywords: Connected component analysis ; Document image processing ; Document segmentation ; Layout extraction ; Mixed mode documents ; Text and nontext separation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Proper processing and efficient representation of the digitized images of printed documents require the separation of the various information types: text, graphics, and image elements. For most applications it is sufficient to separate text and nontext, because text contains the most information. This paper describes the implementation and performance of a robust algorithm for text extraction and segmentation that is completely independent of text orientation and can deal with text in various font styles and sizes. Text objects can be nested in nontext areas, and inverse printing can also be analyzed. It should be mentioned that the classification is based only on rough image features, and individual characters are not recognized. The three main processing steps of the system are the generation of connected components, neighborhood analysis, and generation of text lines and blocks. As output, connected components are classified as text or nontext. Text components are grouped as characters, words, lines, and blocks. Nontext objects are accumulated as a separate nontext block.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01213414
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    Motion estimation methods and noisy phenomena (1994)
    Springer
    Machine vision and applications 7 (1994), S. 247-258 
    Details
    ISSN: 1432-1769
    Keywords: Motion estimation ; Pattern recognition ; Generalized Hough transform ; Crosscorrelation ; Optical flow ; Aperture problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In an infrared surveillance system (which must detect remote sources and thus has a very low resolution) in an aerospace environment, the estimation of the cloudy sky velocity should lower the false alarm rate in discriminating the motion between various moving shapes by means of a background velocity map. The optical flow constraint equation, based on a Taylor expansion of the intensity function, is often used to estimate the motion for each pixel. One of the main problems in motion estimation is that, for one pixel, the real velocity cannot be found because of the aperture problem. Another kinematic estimation method is based on a matched filter [generalized Hough transform (GHT)]: it gives a global velocity estimation for a set of pixels. On the one hand we obtain a local velocity estimation for each pixel with little credibility because the optical flow is so sensitivity to noise; on the other hand, we obtain a robust global kinematic estimation, the same for all selected pixels. This paper aims to adapt and improve the GHT in our typical application in which one must discern the global movement of objects (clouds), whatever their form may be (clouds with hazy edges or distorted shapes or even clouds that have very little structure). We propose an improvement of the GHT algorithm by segmentation images with polar constraints on spatial gradients. One pixel, at timet, is matched with another one at timet + ΔT, only if the direction and modulus of the gradient are similar. This technique, which is very efficient, sharpens the peak and improves the motion resolution. Each of these estimations is calculated within windows belonging to the image, these windows being selected by means of an entropy criterion. The kinematic vector is computed accurately by means of the optical flow constraint equation applied on the displaced window. We showed that, for small displacements, the optical flow constraint equation sharpens the results of the GHT. Thus a semi-dense velocity field is obtained for cloud edges. A velocity map computed on real sequences with these methods is shown. In this way, a kinematic parameter discriminates between a target and the cloudy background.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01213415
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    A low-cost calibration method for automated optical mensuration using a video camera (1994)
    Springer
    Machine vision and applications 7 (1994), S. 259-266 
    Details
    ISSN: 1432-1769
    Keywords: Computer vision ; Automated optical mensuration ; Calibration ; Visual inspection
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Automated optical mensuration gauges the acquired image of the inspected unit while assessing its actual size and shape. The mensuration requires the following preparations: (1) alignment of the video camera perpendicularly to the inspection table, and (2) calibration of the scale ratios of image acquisition, notably, the stretching ratio caused by signal conversion and the magnification ratio of optical coupling. This paper presents the unique two-stage calibration method. The first stage applies the parallelogram conservation property, a property very sensitive to misorientation, to test against the potential misalignment. Once detected, we adjust the misalignment towards orthogonal alignment using image patterns of the calibration template. Then, the second stage determines the scale ratios. The proposed calibration method is suitable for on-site applications, and its implementation cost is low. Sensitivity analysis and experimental results are reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01213416
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...