We consider the consistent digital rays (CDR) of curved rays, which approximates a set of curved rays emanating from the origin by the set of rooted paths (called digital rays) of a spanning tree of a grid graph. Previously, a construction algorithm of CDR for diffused families of curved rays to attain an O(√{n log n}) bound for the distance between digital ray and the corresponding ray is known [Chun et al., 2019]. In this paper, we give a description of the problem as a rounding problem of the vector field generated from the ray family, and investigate the relation of the quality of CDR and the discrepancy of the range space generated from gradient curves of rays. Consequently, we show the existence of a CDR with an O(log ^{1.5} n) distance bound for any diffused family of curved rays.

Abstract We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in $$\mathbb {Z}^d$$ Z d . The construction must be consistent (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with $$\varTheta (\log N)$$ Θ ( log N ) error, where resemblance between segments is measured with the Hausdorff distance, and N is the $$L_1$$ L 1 distance between the two points. This construction was considered tight because of a $$\varOmega (\log N)$$ Ω ( log N ) lower bound that applies to any consistent construction in $$\mathbb {Z}^2$$ Z 2 . In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in d dimensions must have $$\varOmega (\log ^{1/(d-1)}\!N)$$ Ω ( log 1 / ( d - 1 ) N ) error. We tie the error of a consistent construction in high dimensions to the error of similar weak constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with $$o(\log N)$$ o ( log N ) error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. A side result, that we find of independent interest, is the introduction of the bichromatic discrepancy: a natural extension of the concept of discrepancy of a set of points. In this paper, we define this concept and extend known results to the chromatic setting.

We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in ℤ^d. The construction must be consistent (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with Θ(log N) error, where resemblance between segments is measured with the Hausdorff distance, and N is the L₁ distance between the two points. This construction was considered tight because of a Ω(log N) lower bound that applies to any consistent construction in ℤ². In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in d dimensions must have Ω(log^{1/(d-1)} N) error. We tie the error of a consistent construction in high dimensions to the error of similar weak constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with o(log N) error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. In order to show our lower bound, we also consider a colored variation of the concept of discrepancy of a set of points that we find of independent interest.

Representing a family of geometric objects in the digital world where each object is represented by a set of pixels is a basic problem in graphics and computational geometry. One important criterion is the consistency, where the intersection pattern of the objects should be consistent with axioms of the Euclidean geometry, e.g., the intersection of two lines should be a single connected component. Previously, the set of linear rays and segments has been considered. In this paper, we extended this theory to families of curved rays going through the origin. We further consider some psudoline arrangements obtained as unions of such families of rays.

Facial micro-expression recognition has attracted researchers in terms of its objectiveness to reveal the true emotion of a person. However, the limited number of publicly available datasets on micro-expression and its low intensity of facial movements have posed a great challenge to training robust data-driven models for recognition task. In 2019, Facial Micro-Expression Grand Challenge combines three popular datasets, i.e. SMIC, CASME II, and SAMM into a single cross-database which requires the generalization of proposed method on a wider range of subject characteristics. In this paper, we propose a simple yet effective CapsuleNet for micro-expression recognition. The effectiveness of our proposed methods was evaluated on the cross-database micro-expression benchmark using the Leave-One-Object-Out cross-validation. The experiments show that our method achieved superiorly higher results than the baseline method (LBP-TOP) provided and other state-of-the-art CNN models.

We study the problem of efficiently correcting an erroneous product of two $$n\times n$$ matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in $${\tilde{O}}(n^2+kn)$$ time and a deterministic $${\tilde{O}}(kn^2)$$ -time algorithm for this problem (where the notation $${\tilde{O}}$$ suppresses polylogarithmic terms in n and k).

Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact. (1) For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any 3-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) On the 1-skeleton of any 3-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.

Image annotation is a process of finding appropriate semantic labels for images in order to obtain a more convenient way for indexing and searching images on the Web. This article proposes a novel method for image annotation based on combining feature-word distributions, which map from visual space to word space, and word-topic distributions, which form a structure to capture label relationships for annotation. We refer to this type of model as Feature-Word-Topic models. The introduction of topics allows us to efficiently take word associations, such as {ocean, fish, coral} or {desert, sand, cactus}, into account for image annotation. Unlike previous topic-based methods, we do not consider topics as joint distributions of words and visual features, but as distributions of words only. Feature-word distributions are utilized to define weights in computation of topic distributions for annotation. By doing so, topic models in text mining can be applied directly in our method. Our Feature-word-topic model, which exploits Gaussian Mixtures for feature-word distributions, and probabilistic Latent Semantic Analysis (pLSA) for word-topic distributions, shows that our method is able to obtain promising results in image annotation and retrieval.

Image annotation is to automatically associate semantic labels with images in order to obtain a more convenient way for indexing and searching images on the Web. This paper proposes a novel method for image annotation based on feature-word and word-topic distributions. The introduction of topics enables us to efficiently take word associations, such as {ocean, fish, coral}, into image annotation. Feature-word distributions are utilized to define weights in computation of topic distributions for annotation. By doing so, topic models in text mining can be applied directly in our method. Experiments show that our method is able to obtain promising improvements over the state-of-the-art method - Supervised Multiclass Labeling (SML)

The bisector of two nonempty sets P and Q in a metric space is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k ≥ 2 is an integer, is a (k-1)-tuple (C1, C2, ..., Ck-1) such that Ci is the bisector of Ci-1 and Ci+1 for every i= 1, 2, ..., k-1, where C0 = P and Ck = Q. This notion, for the case where P and Q are points in Euclidean plane, was introduced by Asano, Matousek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance trisector in this special case. We prove the existence of a distance k-sector for all k and for every two disjoint, nonempty, closed sets P and Q in Euclidean spaces of any (finite) dimension, or more generally, in proper geodesic spaces (uniqueness remains open). The core of the proof is a new notion of k-gradation for P and Q, whose existence (even in an arbitrary metric space) is proved using the Knaster-Tarski fixed point theorem, by a method introduced by Reem and Reich for a slightly different purpose.

Zone diagram is a variation on the classical concept of a Voronoi diagram. Given n sites in a metric space that compete for territory, the zone diagram is an equilibrium state in the competition. Formally it is defined as a fixed point of a certain "dominance" map.

Given a fixed origin o in the d-dimensional grid, we give a novel definition of digital rays dig(op) from o to each grid point p. Each digital ray dig(op) approximates the Euclidean line segment op between o and p. The set of all digital rays satisfies a set of axioms analogous to the Euclidean axioms. We measure the approximation quality by the maximum Hausdorff distance between a digital ray and its Euclidean counterpart and establish an asymptotically tight Θ(log n) bound in the n x n grid. The proof of the bound is based on discrepancy theory and a simple construction algorithm. Without a monotonicity property for digital rays the bound is improved to O(1). Digital rays enable us to define the family of digital star-shaped regions centered at o which we use to design efficient algorithms for image processing problems.

We consider the dense subgraph problem that extracts a subgraph, with a prescribed number of vertices, having the maximum number of edges (or total edge weight, in the weighted case) in a given graph. We give approximation algorithms with improved theoretical approximation ratios assuming that the density of the optimal output subgraph is high, where density is the ratio of number of edges (or sum of edge weights) to the number of edges in the clique on the same number of vertices. Moreover, we investigate the case where the input graph is bipartite and design a randomized pseudopolynomial time approximation scheme that can become a randomized PTAS, even if the size of the optimal output graph is comparatively small. This is a significant improvement in a theoretical sense, since no constant-ratio approximation algorithm was known previously if the output graph has o ( n ) vertices.

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.

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.

We consider the problem of finding a set of attribute values that give a high quality binary segmentation of a database. The quality of a segmentation is defined by an objective function suitable for the user's objective, such as "mean squared error," "mutual information," or "/spl chi//sup 2/" each of which is defined in terms of the distribution of a given target attribute. Our goal is to find value groups on a given conditional domain that split databases into two segments, optimizing the value of an objective function. Though the problem is intractable for general objective functions, there are feasible algorithms for finding high quality binary segmentations when the objective function is convex, and we prove that the typical criteria mentioned above are all convex. We propose two practical algorithms, based on computational geometry techniques, which find a much better value group than conventional heuristics.

We give an algorithm to compute all the local peaks in the $k$-level o f an arrangement of $n$ lines in $O(n \log n) + \tilde{O}((kn)^{2/3})$ time. We can also find $\tau$ largest peaks in $O(n \log ^2 n) + \tilde{O}((\tau n)^{2/3})$ time. Moreover, we consider the longest edge in a parametric minimum spanning tree (in other words, a bottleneck edge for connectivity), and give an algorithm to compute the parameter value (within a given interval) maximizing/minimizing the length of the longest edge in MST. The time complexity is $\tilde{O}( n^{8/7}k^{1/7} + n k^{1/3})$.

The parametric minimax problem, which finds the parameter value minimizing the weight of a solution of a combinatorial maximization problem, is a fundamental problem in sensitivity analysis. Moreover, several problems in computational geometry can be formulated as parametric minimax problems. The parametric search paradigm gives an efficient sequential algorithm for a convex parametric minimax problem with one parameter if the original non-parametric problem has an efficient parallel algorithm. We consider the parametric minimax problem with d parameters for a constant d, and solve it by using multidimensional version of the parametric search paradigm. As a new feature, we give a feasible region in the parameter space in which the parameter vector must be located.Typical results obtained as applications are: (1) Efficient solutions for some geometric problems, including theoretically efficient solutions for the minimum diameter bridging problem in d-dimensional space between convex polytopes. (2) Parametric polymatroid optimization, for example, O(n log n) time algorithm to compute the parameter vector minimizing k-largest linear parametric elements with d dimensions.

We discuss data mining based on association rules for two numeric attributes and one Boolean attribute. For example, in a database of bank customers, Age and Balance are two numeric attributes, and CardLoan is a Boolean attribute. Taking the pair (Age, Balance) as a point in two-dimensional space, we consider an association rule of the form ((Age,Balance) ∈P)⇒(CardLoan = Yes), which implies that bank customers whose ages and balances fall within a planar region P tend to take out credit card loans with a high probability.We consider two classes of regions, rectangles and admissible (i.e., connected and x-monotone) regions. For each class, we propose efficient algorithms for computing the regions that give optimal association rules for gain, support, and confidence, respectively. We have implemented the algorithms for admissible regions as well as several advanced functions based on them in our data mining system named SONAR (System for Optimized Numeric Association Rules), where the rules are visualized by using a graphic user interface to make it easy for users to gain an intuitive understanding of rules.

We show that for any line l in space, there are at most k(k+1) tangent planes through l to the k-level of an arrangement of concave surfaces. This is a generalization of L. Lovasz's (1971) lemma, which is a key constituent in the analysis of the complexity of k-level of planes. Our proof is constructive, and finds a family of concave surfaces covering the "laminated at-most-k level". As consequences, (1): we have an O((n-k)/sup 2/3/n/sup 2/) upper bound for the complexity of the k-level of n triangle of space, and (2): we can extend the k-set result in space to the k-set of a system of subsets of n points.

We consider the problem of finding a set of k vertices in a graph that are in some sense remote. Stated more formally, given a graph G and an integer k, find a set P of k vertices for which the total weight of a minimum structure on P is maximized. In particular, we are interested in three problems of this type, where the structure to be minimized is a spanning tree ({\sc Remote-MST}), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for {\sc Remote-MST} is exactly 4, while this problem is NP-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.

Article Free Access Share on Distribution of distances and triangles in a point set and algorithms for computing the largest common point sets Authors: Tatsuya Akutsu Human Genome Center, Institute of Medical Science, University of Tokyo, Tokyo 108, Japan Human Genome Center, Institute of Medical Science, University of Tokyo, Tokyo 108, JapanView Profile , Hisao Tamaki IBM Tokyo Research Laboratory, Yamato, Kanagawa 242, Japan IBM Tokyo Research Laboratory, Yamato, Kanagawa 242, JapanView Profile , Takeshi Tokuyama IBM Tokyo Research Laboratory, Yamato, Kanagawa 242, Japan IBM Tokyo Research Laboratory, Yamato, Kanagawa 242, JapanView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 314–323https://doi.org/10.1145/262839.262989Published:01 August 1997Publication History 8citation481DownloadsMetricsTotal Citations8Total Downloads481Last 12 Months14Last 6 weeks7 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 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

Given a huge database, we address the problem of finding association rules for numeric attributes, such as Permission to make digital/hard copies of all or pati of this material for personal or claasroom usc is granted without fee provided that the copies are not made or distributed for pro~t or cornmesvial advantage, the copyright notice, the title of the publication and Its date appear, and notice is given that cop yright is by permission of the ACM, Inc.To copy otherwise, to repubtish, to post on servers or to redistribute to lists, requires specific permission and/or fee.PODS '96, Montreal Quebec Canada

We discuss data mining based on association rules for two numeric attributes and one Boolean attribute. For example, in a database of bank customers, "Age" and "Balance" are two numeric attributes, and "CardLoan" is a Boolean attribute. Taking the pair (Age, Balance) as a point in two-dimensional space, we consider an association rule of the form((Age, Balance) ∈ P) ⇒ (CardLoan = Yes),which implies that bank customers whose ages and balances fall in a planar region P tend to use card loan with a high probability. We consider two classes of regions, rectangles and admissible (i.e. connected and x-monotone) regions. For each class, we propose efficient algorithms for computing the regions that give optimal association rules for gain, support, and confidence, respectively. We have implemented the algorithms for admissible regions, and constructed a system for visualizing the rules.

No abstract available.

Let r be a collection of unbounded z-monotone Jordan arcs intersecting at most twice each other, which we call pseudo-parabolas, since two axis parallel parabolas intersects at most twice.We investigate how to cut pseudo-parabolas into the mum weight matroid base when the weight of each element changes as a quadratic function of a single parameter.1

We consider the Hitchcock transportation problem on n supply points and k demand points when n is much greater than k. The problem can be solved in $O(kn^{2} \log n + n^{2}\log^{2} n)$ time if an efficient minimum-cost flow algorithm is directly applied. Applying a geometric method named splitter finding and a randomization technique, we can improve the time complexity when the ratio c of the maximum supply to the minimum supply is sufficiently small. The expected running time of our randomized algorithm is $O(\frac{kn\log cn}{\log(n/k^{4} \log^{2}k)})$ if $n > k^{4} \log^{2} k$, and $O(k^{5} \log^{2} n \log cn )$ if $n \leq k^{4} \log^{2} k$. If $n = \Omega (k^{4+\epsilon}) (\epsilon > 0)$ and $c = \operatorname{poly}(n)$, the problem is solved in $O(kn)$ time, which is optimal.

Let G be a weighted, complete, directed acyclic graph (DAG), whose edge weights obey the Monge condition.We give an efficient algorithm for finding the minimum weight K-link path between a given pair of vertices for any given K.The time complexity of our algorithm is O(n~=) for the concave case and O (ncr (n) log3 n) for the convex case.Our algorithm uses some properties of DAGs withMonge property together with a refined parametric search technique.We apply our algorithm (for the concave case) to get efficient solutions for the following problems, improving on previous results:(1) Finding the largest K-gon contained in a given polygon.(2) Finding the smallest K-gon that is the intersection of K halfplanes out of of given set of halfplanes defining an n-gon.(3) Computing maximum K-cliques of an interval graph.(4) Computing length limited Huffman codes.(5) Computing optimal discrete quantization.

The authors investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Suppose that one is given a set of n points in general d-dimensional space, S=(p/sub 1/,p/sub 2/, . . ., p/sub n/), and that all points move along different straight lines at different but fixed speeds, i.e., the position of p/sub i/ is a linear function of a real parameter. They investigate the numbers of transitions of MinST and MaxST when t increases from - infinity to + infinity . They assume that the dimension d is a fixed constant. Since there are O(n/sup 2/) distances among n points, there are naively O(n/sup 4/) transitions of MinST and MaxST. They improve these trivial upper bounds for L/sub 1/ and L/sub infinity / distance metrics. Let c/sub p/(n, min) (resp. c/sub p/(n, max)) be the number of maximum possible transitions of MinST (resp. MaxST) in L/sub p/ metric for n linearly moving points. They give the following results; c/sub 1/(n, min)=O(n/sup 5/2/a(n)), c/sub infinity /(n, min)=O(n/sup 5/2/a(n)), c/sub 1/(n, max)=O(n/sup n/) and c/sub infinity /(n, max)=O(n/sup 2/) where O(n) is the inverse Ackermann function. They also investigate two restricted cases.>

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

This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduce several new static and dynamic Voronoi diagrams to solve the problem. It is shown that P can be placed inside Q, using translation and rotation, so that the minimum Euclidean distance between any point on P and any point on Q is maximized in Ο(m4n λ16(mn) log mn) time, where m and n are the numbers of edges of P and Q, respectively, and λ16(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. If only translation is allowed, the problem can be solved in Ο(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximum manner is also considered, and in connection with this problem the dynamic Voronoi diagram of κ rigidly moving sets of n points is investigated. The combinatorial complexity of this canonical dynamic diagram for κn points is shown to be Ο(n2) and Ο(n3κ4 log* κ) for κ = 2, 3 and κ ≥ 4, respectively. Several related problems are also treated in a unified way.