排序方式: 共有18条查询结果,搜索用时 15 毫秒
1.
We use projected Delaunay tetrahedra and a maximum independent set approach to compute large subsets of convex quadrangulations on a given set of points in the plane. The new method improves over the popular pairing method based on triangulating the point set. 相似文献
2.
O. Aichholzer F. Aurenhammer Siu-Wing Cheng N. Katoh G. Rote M. Taschwer Yin-Feng Xu 《Discrete and Computational Geometry》1996,16(4):339-359
We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimum-weight triangulation which can be computed in polynomial time by matching and network-flow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation. 相似文献
3.
Oswin Aichholzer Franz Aurenhammer Thomas Hackl Bettina Speckmann 《Computational Geometry》2009,42(6-7):627-631
In this note we discuss some structural properties of minimum weight pseudo-triangulations of point sets. 相似文献
4.
5.
Franz Aurenhammer 《Discrete and Computational Geometry》1987,2(1):49-64
A criterion is given that decides, for a convex tilingC ofR
d
, whetherC is the projection of the faces in the boundary of some convex polyhedronP inR
d+1. Its applicability is restricted neither by the properties nor by the dimension ofC. It turns out to be conceptually simpler than other criteria and allows the easy examination of various classes of cell complexes. In addition, the criterion is constructive, that is, it can be used to constructP provided it exists.Research was supported by the Austrian Fonds zur Foerderung der wissenschaftlichen Forschung. 相似文献
6.
Oswin Aichholzer Franz Aurenhammer Belén Palop 《Discrete and Computational Geometry》2004,31(1):17-35
The city Voronoi diagram is induced by quickest
paths in the L
1plane, made faster by an isothetic
transportation network. We investigate
the rich geometric and algorithmic properties of city Voronoi diagrams,
and report on their use in processing quickest-path queries.
In doing so, we revisit the fact that not every Voronoi-type
diagram has interpretations in both the
distance model and the wavefront model.
Especially, straight skeletons are a relevant example where an
interpretation in the former model is lacking.
We clarify the relationship between these models, and further draw a
connection to the bisector-defined abstract Voronoi diagram model,
with the particular goal of computing the city Voronoi diagram efficiently. 相似文献
7.
8.
Two general classes of Voronoi diagrams are introduced and, along with their modifications to higher order, are shown to be geometrically related. This geometric background, on the one hand, serves to analyse the size and combinatorial structure and, on the other, implies general and efficient methods of construction for various important types of Voronoi diagrams considered in the literature.Research supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung. 相似文献
9.
Franz Aurenhammer 《Discrete and Computational Geometry》1990,5(1):243-254
A new duality between order-k Voronoi diagrams inE
d and convex hulls inE
d+1 is established. It implies a reasonably simple algorithm for computing the order-k diagram forn points in the plane inO(k
2
n logn) time and optimalO(k(n–k)) space.Research was supported by the Austrian Fond zur Foerderung der wissenschaftlichen Forschung. 相似文献
10.
We introduce and discuss pseudo-simplicial complexes
in ℝd as generalizations of pseudo-triangulations in ℝ2. Our approach is based on the concept of maximal locally convex functions on polytopal domains. 相似文献