We revisit the random-access-machine model in which the input is given on a read-only random-access media, the output is to be produced to a write-only sequential-access media, and in addition there is a limited random-access workspace. The length of the input is N elements, the length of the output is limited by the computation itself, and the capacity of the workspace is O ( S + w ) bits, where S is a parameter specified by the user and w is the number of bits per machine word. We present a state-of-the-art priority queue—called an adjustable navigation pile—for this model. Under some reasonable assumptions, our priority queue supports minimum and insert in O (1) worst-case time and extract in \(O(N/S + \lg S)\) worst-case time, where \(\lg N \leq S \leq N/\lg N\) . We also show how to use this data structure to simplify the existing optimal \(O(N^2/S + N \lg S)\) -time sorting algorithm for this model. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Most of the fingerprint matching techniques require extraction of minutiae that are ridge endings or bifurcations of ridge lines in a fingerprint image. Crucial to this step is either detecting ridges from the gray-level image or binarizing the image and then extracting the minutiae. In this work, we firstly exploit the property of almost equal width of ridges and valleys for binarization. Computing the width of arbitrary shapes is a nontrivial task. So, we estimate the width using Euclidean distance transform (EDT) and provide a near-linear time algorithm for binarization. Secondly, instead of using thinned binary images for minutiae extraction, we detect minutiae straightaway from the binarized fingerprint images using EDT. We also use EDT values to get rid of spurs and bridges in the fingerprint image. Unlike many other previous methods, our work depends minimally on arbitrary selection of parameters.

A zone diagram is a new variation of the classical notion of the Voronoi diagram. Given points (sites) ${\mathbf p}_1,\ldots,{\mathbf p}_n$ in the plane, each ${\mathbf p}_i$ is assigned a region $R_i$, but in contrast to the ordinary Voronoi diagrams, the union of the $R_i$ has a nonempty complement, the neutral zone. The defining property is that each $R_i$ consists of all ${\mathbf x}\in{\mathbb{R}}^2$ that lie closer (nonstrictly) to ${\mathbf p}_i$ than to the union of all the other $R_j$, $j\ne i$. Thus, the zone diagram is defined implicitly, by a “fixed-point property,” and neither its existence nor its uniqueness seem obvious. We establish existence using a general fixed-point result (a consequence of Schauder's theorem or Kakutani's theorem); this proof should generalize easily to related settings, say higher dimensions. Then we prove uniqueness of the zone diagram, as well as convergence of a natural iterative algorithm for computing it, by a geometric argument, which also relies on a result for the case of two sites in an earlier paper. Many challenging questions remain open.

Fingerprint indexing is a key technique in automatic fingerprint identification systems (AFIS). However, handling fingerprint distortion is still a problem. This paper concentrates on a more accurate fingerprint indexing algorithm that efficiently retrieves the topNpossible matching candidates from a huge database. To this end, we design a novel feature based on minutia neighborhood structure (we call this minutia detail and it contains richer minutia information) and a more stable triangulation algorithm (low-order Delaunay triangles, consisting of order 0 and 1 Delaunay triangles), which are both insensitive to fingerprint distortion. The indexing features include minutia detail and attributes of low-order Delaunay triangle (its handedness, angles, maximum edge, and related angles between orientation field and edges). Experiments on databases FVC2002 and FVC2004 show that the proposed algorithm considerably narrows down the search space in fingerprint databases and is stable for various fingerprints. We also compared it with other indexing approaches, and the results show our algorithm has better performance, especially on fingerprints with distortion.

Given points P and Q in the plane, we are interested in separating them by two curves C1 and C2 such that every point of C1 has equal distance to P and to C2, and every point of C2 has equal distance to C1 and to Q. We show by elementary geometric means that such C1 and C2 exist and are unique. Moreover, for P = (0,1) and Q = (0,-1), C1 is the graph of a function ƒ: R → R, C2 is the graph of -f, and f is convex and analytic (i.e., given by a convergent power series at a neighborhood of every point). We conjecture that f is not expressible by elementary functions and, in particular, not algebraic. We provide an algorithm that, given x ∈ R and ε > 0, computes an approximation to f(x) with error at most ε in time polynomial in log 1+|x|/ε.The separation of two points by two "trisector" curves considered here is a special (two-point) case of a new kind of Voronoi diagram, which we call the Voronoi diagram with neutral zone and which we investigate in a companion paper.

We study the problem of rounding a real-valued matrix into an integer-valued matrix to minimize an L p -discrepancy measure between them. To define the L p -discrepancy measure, we introduce a family ${\cal F}$ of regions (rigid submatrices) of the matrix and consider a hypergraph defined by the family. The difficulty of the problem depends on the choice of the region family ${\cal F}$. We first investigate the rounding problem by using integer programming problems with convex piecewise-linear objective functions and give some nontrivial upper bounds for the L p discrepancy. We propose "laminar family" for constructing a practical and well-solvable class of ${\cal F}$. Indeed, we show that the problem is solvable in polynomial time if ${\cal F}$ is the union of two laminar families. Finally, we show that the matrix rounding using L 1 discrepancy for the union of two laminar families is suitable for developing a high-quality digital-halftoning software.

(MATH) We introduce a technique for computing approximate solutions to optimization problems. If X is the set of feasible solutions, the standard goal of approximation algorithms is to compute χ ε X that is an ε-approximate solution in the following sense: d(χ)≤(1+ε)d(χ*) where χ* Ε X is an optimal solution, d : X → 0 is the optimization function to be minimized, and $\vareps>0 is an input parameter. Our approach is to first devise algorithms that compute pseudo ε-approximate solutions satisfying the bound d(χ) ≤ d(χR *) + εR where R>0 is a new input parameter. Here χ* R denotes an optimal solution in the space X R of R-constrained feasible solutions. The parameterization provides a stratification of X in the sense that (1) XR ⊆ XR' , for R < R' and (2) XR = X for R sufficiently large.We first describe a highly efficient scheme for converting a pseudo ε-approximation algorithm into a true ε-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than ε-approximation algorithms.We then apply our technique to two problems in robotics: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in 3D, and (B) d 1-optimal motion for a rod moving amidst polygonal obstacles in 2D. Previously, no true ε-approximation algorithm for (B) was known. For (A), our new solution is not only simpler than two previous solutions but also has a lower complexity (in the algebraic model) measured in terms of the input precision. Note that (A) and (B) are the simplest NP-hard motion planning problems in 3-D and 2-D respectively.

We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of m barriers.We obtain the following results:if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost O(min(m2, mfi)); if the barriers are disjoint line segments, then there is always a spanning tree of cost O(m); if the barriers are disjoint fat objects, discs for example, then there is always a spanning tree of cost O(n + m).All our bounds are worst-case optimal.

Article Free Access Share on Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k Authors: Tetsuo Asano Dept. af Engr. Informatics, Osaka Electro-Communication University, Neyagawa 572, Japan Dept. af Engr. Informatics, Osaka Electro-Communication University, Neyagawa 572, JapanView Profile , Naoki Katoh Dept. of Management Science, Kobe university of Commerce, Kobe 651-21, Japan Dept. of Management Science, Kobe university of Commerce, Kobe 651-21, JapanView Profile , Hisao Tamaki IBM Tokyo Research Laboratory, Yamato 242, Japan IBM Tokyo Research Laboratory, Yamato 242, JapanView Profile , Takeshi Tokuyama IBM Tokyo Research Laboratory, Yamato 242, Japan IBM Tokyo Research Laboratory, Yamato 242, JapanView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 275–283https://doi.org/10.1145/258533.258602Online:04 May 1997Publication History 31citation606DownloadsMetricsTotal Citations31Total Downloads606Last 12 Months51Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article d1-optimal motion for a rod (extended abstract) Share on Authors: Tetsuo Asano Osaka Electro-Communication University, Japan Osaka Electro-Communication University, JapanView Profile , David Kirkpatrick University of British Columbia, Canada University of British Columbia, CanadaView Profile , Chee K. Yap Courant Institute, New York University Courant Institute, New York UniversityView Profile Authors Info & Claims SCG '96: Proceedings of the twelfth annual symposium on Computational geometryMay 1996 Pages 252–263https://doi.org/10.1145/237218.237394Published:01 May 1996 1citation100DownloadsMetricsTotal Citations1Total Downloads100Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper introduces a new digital halftoning technique based on error diffusion along a random space-filling curve. The purpose of introducing randomness is to erase regular patterns which tend to arise in an image area of uniform intensity. For efficient implementation we need to remove long dependency by partitioning the entire image into small square regions. Due to this partition, however, region boundaries may become clearer. For this reason we introduce an adaptive method to distribute error to neighboring pixels based on how many neighboring pixels affect them. Some experimental results are also given.

Article Free Access Share on Walking on an arrangement topologically Authors: Tetsuo Asano Osaka Electro-Communication University Osaka Electro-Communication UniversityView Profile , Leonidas J. Guibas MIT, Stanford University, and DEC Systems Research Center MIT, Stanford University, and DEC Systems Research CenterView Profile , Takeshi Tokuyama IBM Research, Tokyo Research Laboratory IBM Research, Tokyo Research LaboratoryView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 297–306https://doi.org/10.1145/109648.109690Published:01 June 1991Publication History 5citation307DownloadsMetricsTotal Citations5Total Downloads307Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider clustering problems under two different optimization criteria. One is to minimize the maximum intracluster distance (diameter), and the other is to maximize the minimum intercluster distance. In particular, we present an algorithm which partitions a set S of n points in the plane into two subsets so that their larger diameter is minimized in time Ο(n log n) and space Ο(n). Another algorithm with the same bounds computes a k-partition of S for any k so that the minimum intercluster distance is maximized. In both instances it is first shown that an optimal parition is determined by either a maximum or minimum spanning tree of S.

The problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides is discussed. A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate. First, a method of achieving a minimum partition is presented. The number M * of the trapezoids in the minimum partition of a polygonal region P is shown to be M * = n + w - h - d - 1, where n , w , and h are the number of vertices, windows (holes), and horizontal edges of P , respectively, and d is the cardinality of a maximum independent set of the straight-lines-in-the-plane graph associated with P . Next, this problem is shown to be polynomially equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph, and consequently, it is shown to be NP-complete. However, for a polygonal region without windows, an O ( n 2 )-time algorithm for partitioning it into a minimum number of trapezoids is presented. Finally, an O ( n log n )-time approximation algorithm with the performance bound 3 is presented.

Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O(n2) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in O(n2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in O(n2) time, improving earlier O(n2 log n) results.

We present a new routing region definition and ordering (RRDO) scheme for building block layout. Given an arbitrary placement of rectangular blocks (including the case with cycles in the channel precedence constraints), without modifying the placement, our scheme defines and orders channels so that when a new channel is being routed, its width can be expanded or contracted without destroying the previously routed channels. The cycles in the channel precedence constraints are broken by introducing a new kind of channel--the L-shaped channels. Unlike switchboxes, L-shaped channels can be expanded or contracted to permit the completion of routing without rerouting other existing channels. An efficient greedy RRDO algorithm has been implemented, which tries to generate as few L-shaped channels as possible since L-shaped channels are harder to route than straight channels. Our algorithm represents routing regions by a floor plan graph, for which we provide a precise definition and a construction algorithm. The experimental results of the RRDO algorithm are promising.

We consider the problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides. Triangles with a horizontal side are considered to be trapezoids with two horizontal sides one of which is degenerate. In this paper we show that this problem is equivalent to the problem of finding a maximum independent set of a straight-lines-in-the-plane graph. Thus it is shown to be NP-complete. Next we present an O(n log n) natural approximation algorithm which uses only horizontal chords to partition a polygonal region P into trapezoids, where n is the number of vertices of P. We show that the absolute performance ratio of the algorithm is three. We can also design another approximation algorithm with the ratio (1 + 2/c) if we have a (1 - 1/c) approximation algorithm for the maximum independent set problem on straight-lines-in-the-plane graphs, where c is some constant. Finally, we give an O(n3) exact algorithm for polygonal regions without windows.

This paper presents a new pattern router based on an enumeration scheme which sequentially produces alternative paths for a pin pair. First, we represent a pattern or shape of a route by a sequence of symbols representing directions of constituent line segments. Then, we investigate a condition that a sequence of symbols represents a valid pattern. We also count all valid patterns.

This paper deals with a wire-routing algorithm for a building-block LSI. This algorithm has several features which sharply define it from previous techniques. The most noteworthy one among them is that it can achieve perfect wirability. This feature enables a design automation of an LSI layout pattern without any human supports.