We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). Let P be a trapezoided rectilinear simple polygon with n vertices. In O(log n) time using O(n/log n) processors we can optimally compute: 1. Minimum réctilinear link paths, or shortest paths in the L1 metric from any point in P to all vertices of P. 2. Minimum rectilinear link paths from any segment inside P to all vertices of P. 3. The rectilinear window (histogram) partition of P. 4. Both covering radii and vertex intervals for any diagonal of P. 5. A data structure to support rectilinear link-distance queries between any two points in P (queries can be answered optimally in O(log n) time by uniprocessor). Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequential algorithm for this problem which used O(n log n) time and space.5 We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.
We consider a problem which can greatly enhance the areas of cursive script recognition and the recognition of printed character sequences. This problem involves recognizing words/strings by processing their noisy subsequences. Let X* be any unknown word from a finite dictionary H. Let U be any arbitrary subsequence of X*. We study the problem of estimating X* by processing Y, a noisy version of U. Y contains substitution, insertion, deletion and generalized transposition errors — the latter occurring when transposed characters are themselves subsequently substituted. We solve the noisy subsequence recognition problem by defining and using the constrained edit distance between X ε H and Y subject to any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm to compute this constrained edit distance has been presented. Using these algorithms we present a syntactic Pattern Recognition (PR) scheme which corrects noisy text containing all these types of errors. Experimental results which involve strings of lengths between 40 and 80 with an average of 30.24 deleted characters and an overall average noise of 68.69 % demonstrate the superiority of our system over existing methods.
The core refractive index of Corning SMF-28 optical fibre exposed to ArF laser pulses increases with the square of the fluence per pulse. Bragg gratings with a refractive index modulation amplitude higher than 10
-3 have been obtained. This is an order of magnitude improvement over previously reported values for this type of fibre in the absence of treatment to enhance the photosensitivity.
An apodized in-fibre Bragg grating reflector is fabricated using the phase mask photoimprinting technique. The reflector has a centre wavelength of 1550 nm, a bandwidth of 0.22 nm and a peak reflectivity of 90%. At 0.4 nm (50 GHz) from the centre wavelength the reflectivity is 40 dB lower than the peak reflectivity; this is an improvement of more than 20 dB over an unapodized Bragg grating reflector with similar bandwidth and peak reflectivity.
A variable diffraction efficiency phase mask is produced by focused ion beam, implanting a grating pattern into a fused SiO
2 substrate with a 100-nm-diam, 200keV Si beam. The substrate is prepared by cleaning and coating with a 20-nm-thick film of Al to dissipate the ion charge. The pattern consists of 930 lines, each 80μm long, at a pitch of 1.075μm, to obtain a 1-mm-long grating. The substrate is wet etched in a 1M% HF solution for about 45min to produce a phase mask with the desired diffraction efficiency. This phase mask is used to photoimprint Bragg gratings into standard hydrogenated single-mode telecommunication fibers using 193nm light from an ArF laser.