Helmut Alt

TCS Journal 2012 Journal Article

Shape matching by random sampling

• Helmut Alt
• Ludmila Scharf

In order to determine the similarity between two planar shapes, which is an important problem in computer vision and pattern recognition, it is necessary to first match the two shapes as well as possible. As sets of allowed transformation to match shapes we consider translations, rigid motions, and similarities. We present a generic probabilistic algorithm based on random sampling for matching shapes which are modelled by sets of curves. The algorithm is applicable to the three considered classes of transformations. We analyze which similarity measure is optimized by the algorithm and give rigorous bounds on the number of samples necessary to get a prespecified approximation to the optimal match within a prespecified probability.

SODA Conference 2003 Conference Paper

Matching planar maps

• Helmut Alt
• Alon Efrat
• Günter Rote
• Carola Wenk

MFCS Conference 1986 Conference Paper

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones

• Helmut Alt
• Torben Hagerup
• Kurt Mehlhorn
• Franco P. Preparata

Abstract We describe a deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM's shared memory is polynomial in n, each PRAM step is simulated by O (log n ) MPC steps or by O ((log n ) 2 ) steps of the bounded degree network. This improves upon a previous result by Upfal and Wigderson. We also prove an Ω((log n ) 2 /log log n ) lower bound on the number of steps needed to simulate one PRAM step on a bounded degree network under the assumption that the communication in the network is point-to-point.

TCS Journal 1985 Journal Article

Multiplication is the easiest nontrivial arithmetic function

• Helmut Alt

It is shown that fixed point multiplication can be reduced to the evaluation of any member of a very large class of functions including most of the nontrivial functions used in practice. That means that whenever any such function can be evaluated by a Boolean circuit of size S(n), multiplication can be done with O(S(n)) Boolean operations, as well.

STOC Conference 1984 Conference Paper

Comparison of Arithmetic Functions with Respect to Boolean Circuit Depth (Extended Abstract)

• Helmut Alt

FOCS Conference 1983 Conference Paper

Multiplication Is the Easiest Nontrivial Arithmetic Function

• Helmut Alt

It is shown that floating point (or integer) multiplication can be reduced to the evalution of a very large class of functions including most of the nontrivial functions used in practice. That means that whenever any such function can be evaluated by boolean circuits of size S(n), then multiplication can be done with circuits of size O(S(n)). as well.

MFCS Conference 1981 Conference Paper

Partial Match Retrieval in Implicit Data Structures

• Helmut Alt
• Kurt Mehlhorn
• J. Ian Munro