Zobrazeno 1 - 10
of 82
pro vyhledávání: '"Raimund Seidel"'
A {\em simple drawing} $D(G)$ of a graph $G$ is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge $e$ in the complement of $G$ can be {\em inserted} into $D(G)$ if there exists a simple drawi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eeb6cffc787d790c529dba0555c8eae4
http://arxiv.org/abs/1909.07347
http://arxiv.org/abs/1909.07347
Publikováno v:
Computer-Aided Design. 70:46-55
We define the Average Curve (AC) of a compatible set of two or more smooth and planar, Jordan curves. It is independent of their order and representation. We compare two variants: the valley AC (vAC), defined in terms of the valley of the field that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::00a5ece5133f3dcd46c6cb07f25bee57
https://doi.org/10.1016/j.cad.2015.06.017
https://doi.org/10.1016/j.cad.2015.06.017
Publikováno v:
Computational Geometry. 46:615-630
Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@?"1"= "j"= =3 odd, where n"i spheres have rad
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c8eca4d971e44378be89e3aba1b120f4
https://doi.org/10.1016/j.comgeo.2013.02.001
https://doi.org/10.1016/j.comgeo.2013.02.001
Autor:
Raimund Seidel
Publikováno v:
Computational Geometry. 43(6-7):556-564
This paper presents a very simple incremental randomized algorithm for computing the trapezoidal decomposition induced by a set S of n line segments in the plane. If S is given as a simple polygonal chain the expected running time of the algorithm is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bbca139f6a6da15041b41affce35276f
Publikováno v:
International Journal of Computational Geometry & Applications. 15:463-475
Given a set S of s points in the plane, where do we place a new point, p, in order to maximize the area of its region in the Voronoi diagram of S and p? We study the case where the Voronoi neighbors of p are in convex position, and prove that there i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a3d949bf8d05d4647390d6b97231d224
https://doi.org/10.1142/s0218195905001786
https://doi.org/10.1142/s0218195905001786
Autor:
Micha Sharir, Raimund Seidel
Publikováno v:
SIAM Journal on Computing. 34:515-525
We present a new analysis of the worst-case cost of path compression, which is an operation that is used in various well-known "union-find" algorithms. In contrast to previous analyses which are essentially based on bottom-up approaches, our method p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f5619ae7485d35c425d82232cee290d3
https://doi.org/10.1137/s0097539703439088
https://doi.org/10.1137/s0097539703439088
Autor:
Raimund Seidel, Udo Adamy
Publikováno v:
Journal of Algorithms. 37:189-217
What is the smallest constant c so that the planar point location queries can be answered in clog2n+o(logn) steps (i.e., point?line comparisons) in the worst case? M. T. Goodrich, M. Orletsky, and K. Ramaiyer (1997, in “Proc 8th ACM-SIAM Symp on Di
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3402d130d082423c634f1375c7ac02d7
https://doi.org/10.1006/jagm.2000.1101
https://doi.org/10.1006/jagm.2000.1101
Autor:
Raimund Seidel
Publikováno v:
Discrete & Computational Geometry. 19:1-17
This paper addresses some fundamental questions concerning perturbations as they are used in computational geometry. How does one define them? What does it mean to compute with them? How can one compute with them? Is it sensible to use them? We defin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::de08faa772afe80503e42025f56222f6
https://doi.org/10.1007/pl00009330
https://doi.org/10.1007/pl00009330
Publikováno v:
Computational Geometry. 7(5-6):265-301
A convex polytope P can be specified in two ways: as the convex hull of the vertex set V of P , or as the intersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is to compute V from H>. The facet enumeration proble
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::32b2bc808064681c9edd6e03434b2fe1
Autor:
Raimund Seidel
Publikováno v:
Journal of Computer and System Sciences. 51(3):400-403
We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted n-vertex graphs in time O(M(n) log n), where M(n) denotes the time necessary to multiply two n × n matrices of small int
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::80b4656a71c5a8c52acbcd28fdc91c57