Catálogo de publicaciones - libros

A point is 1-well illuminated by a set of point lights if there is, at least, one light interior to each half-plane with on its border. We consider the illumination range of the lights as a parameter to be optimized. So we minimize the lights’ illumination range to 1-well illuminate a given point . We also present two generalizations of 1-good illumination: the orthogonal good illumination and the good Θ-illumination. For the first, we propose an optimal linear time algorithm to optimize the lights’ illumination range to orthogonally well illuminate a point. We present the E-Voronoi Diagram for this variant and an algorithm to compute it that runs in time. For the second and given a fixed angle Θ ≤ , we present a linear time algorithm to minimize the lights’ illumination range to well Θ-illuminate a point.

A chain or -link is a sequence of links whose lengths are fixed joined together from their endpoints, free to turn about their endpoints, which act as joints. “”, which is NP-Complete is to find the minimum length of the folded chain in one dimensional space. The best result for ruler folding problem is reported by Hopcroft et al. in one dimensional space which requires () time complexity, where is length of the longest link in the chain and links have integer value lengths. We propose a dynamic programming approach to fold a given chain whose links have integer lengths in a minimum length in () time and space. We show that by generalizing the algorithm it can be used in -dimensional space for such that it requires (2) time using (2) space.

Let and be two colored point sets in , with . We propose a process for determining matches, in terms of the distance, between and subsets of under color preserving rigid motion, assuming that the position of all colored points in both sets contains a certain amount of ”noise”. The process consists of two main stages: a lossless filtering algorithm and a matching algorithm. The first algorithm determines a number of andidate zones which are regions that contain a subset of such that may match one or more subsets of . We use a compressed quadtree to have easy access to the subsets of related to candidate zones and store geometric information that is used by the lossless filtering algorithm in each quadtree node. The second algorithm solves the colored point set matching problem: we generate all, up to a certain equivalence, possible motions that bring close to some subset of every and seek for a matching between sets and . To detect these possible matchings we use a bipartite matching algorithm that uses Skip Quadtrees for neighborhood queries. We have implemented the proposed algorithms and report results that show the efficiency of our approach.

We describe an ()-time algorithm for computing a minimum-area convex polygon that intersects a set of isothetic line segments.

Protein consists of a set of atoms. Given a protein, the molecular surface of the protein is defined with respect to a probe approximating a solvent molecule. This paper presents an efficient, as efficient as the realtime, algorithm to triangulate the blending surfaces which is the most critical subset of a molecular surface. For the quick evaluation of points on the surface, the proposed algorithm uses masks which are similar in their concepts to those in subdivision surfaces. More fundamentally, the proposed algorithm takes advantage of the concise representation of topology among atoms stored in the -shape which is indeed used in the computation of the blending surface itself. Given blending surfaces and the corresponding -shape, the proposed algorithm triangulates the blending surfaces in ( ·) time in the worst case, where is the number of boundary atoms in the protein and is the number of point evaluations on a patch in the blending surface.

Determining whether two segments and in a planar polygonal scene see each other is a classical problem in computational geometry. In this problem we seek for a segment connecting two points of and without intersecting edges of the scene. In planar polygonal scenes, this problem is -hard and its time complexity is () where is the complexity of the scene. This problem can be defined in the same manner when and are any kind of objects in the plane. In this paper we consider this problem when and can be points, segments or convex polygons. We preprocess the scene so that for any given pair of query objects we can solve the problem efficiently. In our presented method, we preprocess the scene in () time to build data structures of () total size by which the queries can be answered in () time. Our method is based on the extended visibility graph [1] and a range searching data structure presented by Chazelle [2].

We consider geometric shortest path queries between arbitrary pairs of objects on a connected polyhedral surface of genus . The query objects are points, vertices, edges, segments, faces, chains, regions and sets of these. The surface consists of positively weighted triangular faces. The cost of a path on is the weighted sum of Euclidean lengths of the sub-paths within each face of . We present generic algorithms which provide approximate solutions.

Recently in [12] a deterministic worst-case upper bound was shown for the problem of covering a set of integer-coordinate points in the plane with axis-parallel rectgangles minimizing a certain objective function on rectangles. Because the rectangles have to meet a lower bound condition for their side lengths, this class of problems is termed . The present paper is devoted to show that the bounds for solving this 1-sided problem class also hold for problem variants with length constraints on coverings meaning that the rectangles are subjected also to an upper bound for side lengths. All these 2-sided variants are NP-hard. We also provide a generalization of the results to the -dimensional case.

This paper proposes a new algorithm for querying the shortest path between two points and in a simple polygon based on Voronoi diagram(VD). Based on the polygon’s VD, we first find the Voronoi skeleton path (,) from point to , and then along which we compute the shortest path (,) by visibility computing simultaneously. (,) can be reported in time (). It can be used in our 3D virtual museum system, in which the polygon’s VD is used as a data structure for path planning, visibility computing, collision detection, and so on.

A linear axis is a skeleton recently introduced for simple polygons by Tanase and Veltkamp. It approximates the medial axis up to a certain degree, which is controlled by means of parameter > 0. A significant advantage of a linear axis is that its edges are straight line segments. We generalize the notion of a linear axis and the algorithm for its efficient computation to the case of general polygons, which might contain holes. We show that a linear axis -equivalent to the medial axis can be computed from the latter in linear time for almost all general polygons. If the medial axis is not pre-computed, and the polygon contains holes, this implies (log) total computation time for a linear axis.