European Workshop on Computational Geometry (20th. 2004. Sevilla)

URI permanente para esta colecciónhttps://hdl.handle.net/11441/54808

Examinar

Mostrando 1 - 20 de 56

Computing the Hausdorff distance between curved objets
(2004) Alt, Helmut; Scharf, Ludmila
Unfolding simple chains inside circles
(2004) Eskandari, Marzieh; Mohades, Ali
It is an open problem to determined whether a polygonal chain can be straightened inside a confi ning region if its links are not allowed to cross. In this paper we propose a special case: whether a polygonal chain can be straightened inside a circle without allowing its links to cross. We prove that this is possible if the straightened confi guration can fi t within circle. Then we show that these simple chains have just one equivalence class of confi gurations.
Distributed ranking methods for geographic information retrieval
(2004) Kreveld, Marc van; Reinbacher, Iris; Arampatzis, Avi
Geographic Information Retrieval is concerned with retrieving documents that are related to some location. This paper addresses the ranking of documents by both textual relevance and spatial relevance. To this end, we introduce distributed ranking, where similar documents are ranked spreaded in the list instead of sequentially. The effect of this is that documents close together in the ranked list have less redundant information. We present various ranking methods and efficient algorithms for them.
Triangulations without pointed spanning trees
(2004) Aichholzer, Oswin; Huemer, Clemens; Krasser, Hannes
Problem 50 in the Open Problems Project asks whether any triangulation on a point set in the plane contains a pointed spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there exist triangulations which require a linear number of edge flips to become Hamiltonian.
Improved results for the k-centrum straight-line location problem
(2004) Lozano Palacio, Antonio José; Mesa López-Colmenar, Juan Antonio; Plastria, Frank; Universidad de Sevilla. Departamento de Matemática Aplicada II
The k-Centrum problem consists in finding a point that minimises the sum of the distances to the k farthest points out of a set of given points. It encloses as particular cases to two of the most known problems in Location Analysis: the center, also named as the minimum enclosing circle, and the median. In this paper the k-Centrum criteria is applied to obtaining a straight line-shaped facility. A reduced finite dominant set is determined and an algorithm with lower complexity than the previous one obtained.
New bound for incremental constructing arrangements of curves
(2004) Abellanas Oar, Manuel; Calatayud Ramos, Aymée; García López, Jesús
Let A(Γ) be the arrangement induced by a set Γ of n unbounded Jordan curves in the plane that intersect each other in at most two points. The upper bound for constructing those arrangements by an incremental method is, up to now, O(nλ4(n)). In this paper we improve this bound to O(nλ3(n)).
The minimum Manhattan network problem approximations and exact solutions
(2004) Benkert, Marc; Shirabe, Takeshi; Wolff, Alexander
A Manhattan p–q path is a geodesic in the Manhattan (or L1-) metric that connects p and q, i.e. a staircase path between p and q. Given a set of points P in the plane, a Manhattan network is a set of axis-parallel line segments that contains a Manhattan p–q path for each pair {p, q} of points in P. In this paper we consider the minimum Manhattan network problem which consists of finding a Manhattan network of minimum total length, an MMN in short, i.e. a 1-spanner for the Manhattan metric. The problem is likely to have applications in VLSI layout. Its complexity status is unknown. The problem has been considered before. Gudmundsson et al. have proposed a factor-8 O(n log n)-time and a factor-4 O(n3)-time approximation algorithm, where n is the number of input points. Later Kato et al. have given a factor-2 O(n3)-time approximation algorithm. However, their correctness proof is incomplete. In this paper we give a geometric factor-3 approximation algorithm that runs in O(n log n) time and the first mixed-integer programming (MIP) formulation for the MMN problem. We have implemented and evaluated both approaches.
Maximum weight triangulation of a special convex polygon
(2004) Qian, Jianbo; Wang, Cao An
In this paper, we investigate the maximum weight triangulation of a special convex polygon, called `semi-circled convex polygon'. We prove that the maximum weight triangulation of such a polygon can be found in O(n2) time.
Warping cubes: better triangles from marching cubes
(2004) Tzeng, LeeAnn
Defining discrete Morse functions on infinite surfaces
(2004) Ayala Gómez, Rafael; Fernández Fernández, Luis Manuel; Universidad de Sevilla. Departamento de Geometría y Topología; Universidad de Sevilla. FQM189: Homotopía Propia; Universidad de Sevilla. FQM327: Geometría (Semi) Riemanniana y Aplicaciones
We present an algorithm which defines a discrete Morse function in Forman’s sense on an infinite surface including a study of the minimality of this function.
Partitioning orthogonal polygons by extension of all edges incident to reflex vertices: lower and upper bounds on the number of pieces
(2004) Bajuelos Domínguez, António Leslie; Tomás, Ana Paula; Marques, Fábio José Reis Luís
Given an orthogonal polygon P, let |Π(P)| be the number of rectangles that result when we partition P by extending the edges incident to reflex vertices towards INT(P). In Tomás, A. P., Bajuelos, A. L., Marques, F.: Approximation algorithms to minimum vertex cover problems on polygons and terrains. In P.M.A Sloot et al. (Eds): Proc. of ICCS 2003, LNCS 2657, SpringerVerlag (2003) 869-878. we showed that |Π(P)| ≤ 1 + r + r 2, where r is the number of reflex vertices of P. We shall now give sharper bounds both for maxP |Π(P)| and minP |Π(P)|. Moreover, we characterize the structure of orthogonal polygons in general position for which these new bounds are exact.
Quadratic-time, linear-space algorithms for generating orthogonal polygons with a given number of vertices
(2004) Tomás, Ana Paula; Bajuelos Domínguez, António Leslie
Straight line skeleton in linear time, topologically equivalent to the medial axis
(2004) Tanase, Mirela; Veltkamp, Remco C.
Approximate range searching using binary space partitions
(2004) Berg, Mark de; Streppel, Micha
A simple and less slow method for counting triangulations and for related problems
(2004) Ray, Saurabh; Seidel, Raimund
We present a simple dynamic programming based method for counting straight-edge triangulations of planar point sets. This method can be adapted to solve related problems such as nding the best triangulation of a point set according to certain optimality criteria, or generating a triangulation of a point set uniformly at random. We have implemented our counting method. It appears to be substantially less slow than previous methods: instances with 20 points, which used to take minutes, can now be handled in less than a second, and instances with 30 points, which used to be solvable only by employing several workstations in parallel over a substantial amount of time, an now be solved in about one minute on a single standard workstation.
New lower bounds for the number of straight-edge triangulations of a planar point set
(2004) McCabe, Paul; Seidel, Raimund
We present new lower bounds on the number of straight-edge triangulations that every set of n points in plane must have. These bounds are better than previous bounds in case of sets with either many or few extreme points.
Verification of partitions of 2d and 3d objects
(2004) Palios, Leonidas
We consider the problems of deciding whether a given collection of polygons (polyhedra resp.) forms (i) a partition or (ii) a cell complex decomposition of a given polygon (polyhedron resp.). We describe simple O(n log n)-time and O(n)-space algorithms for these problems, where n is the total description size of the input. If, in the input, vertices are referenced by means of indices to an array of distinct vertices, then our cell complex decomposition verification algorithms run in O(n) time.
Guarding art galleries by guarding witnesses
(2004) Chwa, Kyung-Yong; Jo, Byung-Cheol; Knauer, Christian; Moet, Esther; Oostrum, René van; Shin, Chan-Su
Let P be a simple polygon. We de ne a witness set W to be a set of points su h that if any (prospective) guard set G guards W, then it is guaranteed that G guards P . We show that not all polygons admit a nite witness set. If a fi nite minimal witness set exists, then it cannot contain any witness in the interior of P ; all witnesses must lie on the boundary of P , and there an be at most one witness in the interior of any edge. We give an algorithm to compute a minimal witness set for P in O(n2 log n) time, if such a set exists, or to report the non-existence within the same time bounds. We also outline an algorithm that uses a witness set for P to test whether a (prospective) guard set sees all points in P.
On geometric properties of enumerations of axis-parallel rectangles
(2004) Vyatkina, Kira
We show that for any set of non-overlapping axis-parallel rectangles in the plane, there exists a sloping enumeration, such that the numbers of rectangles intersected by any line with a non-negative slope increase along this line. Such enumeration can be computed in the optimal time Θ(n log n) using linear space. The notion of a sloping enumeration can be generalized to higher dimensions; however, already in three-dimensional space it may not exist. We also consider a strip packing problem for a set of rectangles with a fixed enumeration, which is required to be sloping for the resulting packing. This problem is proved to be NP-hard in any dimension d ≥ 2.
Balanced intervals of two stes of points on a line or circle
(2004) Kaneko, Atsushi; Kano, Mikio
Let n,m, k, h be positive integers such that 1 ≤ n ≤ m, 1 ≤ k ≤ n and 1 ≤ h ≤ m. Then we give a necessary and sufficient condition for every configuration with n red points and m blue points on a line or circle to have an interval containing precisely k red points and h blue points.

Examinar

Envíos recientes