The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We present two versions of an algorithm based on the reverse search technique for enumerating all k-sets of a point set in ℝd. The key elements include the notion of a k-set polytope and the optimization of a linear function over a k-set polytope. In addition, we obtain several results related to the k-set polytopes. Among others, we show that the 1-skeleton of a k-set polytope...
We study the C-oriented line simplification problem: Given a polygonal chain P represented by an ordered set of vertices p1,...,pn in the plane, a set of orientations C, and a constant ∈, we search for a “C-oriented” polygonal chain Q consisting of the minimum number of line segments that has distance at most ε to P in the Fréechet metric. A polygonal...
Given a graph G with weighted edges, and a subset of nodes T, the T-join problem asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u ∈ T. We describe the applications of the T-join problem in sparse graphs to the phase assignment problem in VLSI mask layout and to conformal refinement of finite element meshes. We suggest a practical algorithm for...
We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l..l + n − 1], of fixed-size elements, as elements are added to or removed from one or both ends. Our structures also support access to the element in position i. All operations are performed in constant time. The extra space (i.e., the space used past storing...
A new way of constructing (minimal) perfect hash functions is described. The technique considerably reduces the overhead associated with resolving buckets in two-level hashing schemes. Two memory probes suffice for evaluation of the function. This improves the probe performance of previous minimal perfect hashing schemes, and is shown to be optimal.
Shared-memory multiprocessors feature parallelism and a steep cache hierarchy, two salient characteristics that distinguish them from the commodity processors of ten years ago. Both of these characteristics can be exploited effectively using the same general strategy: divide-and-conquer recursion. This talk overviews the Cilk multithreaded programming language being developed in the MIT Laboratory...
We consider three closely related optimization problems, arising from the graph drawing and the VLSI research areas, and conjectured to be NP-hard, and we prove that, in fact, they are NP-complete. Starting from an orthogonal representation of a graph, i.e., a description of the shape of the edges that does not specify segment lengths or vertex positions, the three problems consist of providing an...
Aicholzer et al. recently presented a new geometric construct called the straight skeleton of a simple polygon and gave several combinatorial bounds for it. Independently, the current authors defined in companion papers a distance function based on the same offsetting function for convex polygons. In particular, we explored the nearest- and furthest- neighbor Voronoi diagrams of this function and...
A new measure, the accommodating function, for the quality of on-line algorithms is presented. The accommodating function, which is a generalization of both the competitive ratio and the accommodating ratio, measures the quality of an on-line algorithm as a function of the resources that would be sufficient for some algorithm to fully grant all requests. More precisely, if we have some amount of resources...
We consider the approximability of the TSP problem in graphs that satisfy a relaxed form of triangle inequality. More precisely, we assume that for some parameter τ ≥ 1, the distances satisfy the inequality dist(x,y) ≤τ. (dist(x,z)+ dist(z,y)) for every triple of vertices x, y, and z. We obtain a 4τ approximation and also show that for some ∈ > 0 it is NP-hard to obtain a (1 + ∈τ) approximation...
In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot position and orientation in the map, is correct for the world G. We consider the world model with a graph G = (VG,EG...
We consider the on-line navigation problem of a robot inside an unknown polygon P. The robot has to find a path from a starting point to an unknown goal point and it is equipped with on-board cameras through which it can get the visibility map of its immediate surroundings. It is known that if P is a street with respect to two points s and t then starting at s the robot can find t with a constant...
We study the problem of scheduling a set of n independent tasks on a fixed number of parallel processors, where the execution time of a task is a function of the subset of processors assigned to the task. We propose a fully polynomial approximation scheme that for any fixed ∈ > 0 finds a preemptive schedule of length at most (1 + ∈) times the optimum in O(n) time.We also discuss the non-preemptive...
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. The worker’s objective may be to minimize the amount of work he does (he is “lazy”). He is subject to a constraint that he must be busy when there is work that he can do; we make this notion precise, particularly when preemption is allowed. The resulting class...
This paper describes a method for cloning faces from two orthogonal pictures and for generating populations from a small number of these clones. An efficient method for reconstructing 3D heads suitable for animation from pictures starts with the extraction of feature points from the orthogonal picture sets. Data from several such heads serve to statistically infer the parameters of the multivariate...
We consider the problem of testing the roundness of a manufactured ball, using the finger probing model of Cole and Yap [4]. When the center of the object is known, a procedure requiring O(n2) probes and O(n2) computation time is described. (Here n = |1/q|, where q is the quality of the object.) When the center of the object is not known, the procedure requires O(n ...
We introduce and study a problem that we refer to as the optimal split tree problem. The problem generalizes a number of problems including two classical tree construction problems including the Huffman tree problem and the optimal alphabetic tree. We show that the general split tree problem is NP-complete and analyze a greedy algorithm for its solution. We show that a simple modification of the greedy...
This paper focuses on space efficient representations of trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our attention to trees of higher degree. We consider both cardinal trees (rooted trees where each node has k positions each of which may have a reference to a child) and ordinal trees (the children of each node are simply...
The indexing problem is the one where a text is preprocessed and subsequent queries of the form: “Find all occurrences of pattern P in the text” are answered in time proportional to the length of the query and the number of occurrences. In the dictionary matching problem a set of patterns is preprocessed and subsequent queries of the form: “Find all occurrences of dictionary patterns in text T” are...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.