Mostrando ítems 1-20 de 56

(2004)
• #### Unfolding simple chains inside circles ﻿ [Ponencia]

(2004)
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 ...
• #### Distributed ranking methods for geographic information retrieval ﻿ [Ponencia]

(2004)
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 ...
• #### Triangulations without pointed spanning trees ﻿ [Ponencia]

(2004)
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 ...
• #### Improved results for the k-centrum straight-line location problem ﻿ [Ponencia]

(2004)
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 ...
• #### New bound for incremental constructing arrangements of curves ﻿ [Ponencia]

(2004)
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 ...
• #### The minimum Manhattan network problem approximations and exact solutions ﻿ [Ponencia]

(2004)
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 ...
• #### Maximum weight triangulation of a special convex polygon ﻿ [Ponencia]

(2004)
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.

(2004)
• #### Defining discrete Morse functions on infinite surfaces ﻿ [Ponencia]

(2004)
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 ﻿ [Ponencia]

(2004)
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.: ...

(2004)

(2004)

(2004)
• #### A simple and less slow method for counting triangulations and for related problems ﻿ [Ponencia]

(2004)
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 ...
• #### New lower bounds for the number of straight-edge triangulations of a planar point set ﻿ [Ponencia]

(2004)
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 ﻿ [Ponencia]

(2004)
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 ...
• #### Guarding art galleries by guarding witnesses ﻿ [Ponencia]

(2004)
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 ...
• #### On geometric properties of enumerations of axis-parallel rectangles ﻿ [Ponencia]

(2004)
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 ...
• #### Balanced intervals of two stes of points on a line or circle ﻿ [Ponencia]

(2004)
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 ...