On the Shape of a Set of Points in the Plane (2009)
L I. Gurantz, S. Blake, E. Hoversten, J. Petranovich, A High, Herbert Edelsbrunner, ...
The authors express their appreciation for numerous constructive suggestions, which led to improvements on various phases of the manuscript, to Dr. Marvin Simon of JPL and to Professor George L....
On the Complexity of Umbra and Penumbra (2009)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
On the Complexity of Umbra and Penumbra (2009)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Upper Bound on the Number of Vertices of Polyhedrawith (2008)
Khaled Elbassioni, Zvi Lotker, Raimund Seidel
Abstract In this note we give upper bounds for the number of vertices of the polyhedron P (A, b) = {x 2 Rd: Ax < = b} when the m * d constraint matrix A is subjectedto certain restriction. For...
Raimund Seidel, Nicola Wolpert
We consider the problem of computing a representation of the plane graph induced by one (or more) algebraic curves in the real plane. We make no assumptions about the curves, in particular we allow...
Between umbra and penumbra (2008)
Julien Demouth, Olivier Devillers, Hazel Everett, Sylvain Lazard, Raimund Seidel
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Raimund Seidel, Fachberich Informatik
We present a randomized strategy for maintaining balance in dynamically changing search trees that has optimal expected behavior. In particular, in the expected case a search or an update takes...
08081 Abstracts Collection -- Data Structures (2008)
Arge, Lars, Sedgewick, Robert, Seidel, Raimund
From February 17th to 22nd 2008, the Dagstuhl Seminar 08081 ``Data Structures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. It brought together 49...
On the Complexity of Umbra and Penumbra (2007)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
On the Complexity of Umbra and Penumbra (2007)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Between umbra and penumbra (2007)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Between umbra and penumbra (2007)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
On Computing the Centroid of the Vertices of an Arrangement and Related Problems (2007)
Ajwani, Deepak, Ray, Saurabh, Seidel, Raimund, Tiwary, Hans Raj
ii Datum des Kolloquiums: 14. 05. 2007 (2006)
Annamária Kovács, Dekan Prof, Dr. Thorsten Herfet, Vorsitzender Prof, Dr. Raimund Seidel, ...
iii Abstract. The thesis deals with problems from two distint areas of scheduling theory. In the first part we consider the preemptive Sum Multicoloring (pSMC) problem. In an instance of pSMC,...
Upper bound on the number of vertices of polyhedra with 0, 1-constraint matrices (2006)
Elbassioni, Khaled, Lotker, Zvi, Seidel, Raimund
In this note we give upper bounds for the number of vertices of the polyhedron $P(A,b) = \{x \in Rd: Ax < b\}$ when the $m \times d$ constraint matrix $A$ is subjected to certain restriction. For...
Upper Bound on the Number of Vertices of Polyhedra with $0,1$-Constraint Matrices (2005)
Elbassioni, Khaled, Lotker, Zvi, Seidel, Raimund
In this note we show that the maximum number of vertices in any polyhedron $P=\{x\in \mathbb{R}^d : Ax\leq b\}$ with $0,1$-constraint matrix $A$ and a real vector $b$ is at most $d!$.
Maximizing a Voronoi Region: The Convex Case (2005)
Frank Dehne, Rolf Klein, Raimund Seidel
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...
On the Exact Computation of the Topology of Real Algebraic Curves (2005)
Seidel, Raimund, Wolpert, Nicola, Mitchell, Joseph S. B., Rote, Günter
We consider the problem of computing a representation of the plane graph induced by one (or more) algebraic curves in the real plane. We make no assumptions about the curves, in particular we allow...
sind Eigentum der jeweiligen Inhaber. Tag des Kolloquiums: 16.12.2004 (2004)
Sebastian Winkel, Dekan Prof, Dr. Jörg Eschmeier, Gutachter Prof, Dr. Reinhard Wilhelm, Vorsitzender Prof, ...
On the Itanium 2 processor, effective global instruction scheduling is crucial to high performance. At the same time, it poses a challenge to the compiler: This code generation subtask involves...
der Naturwissenschaftlich-Technischen Fakultäten (2004)
René Beier, Dekan Prof, Dr. Jörg Eschmeier, Vorsitzender Prof, Dr. Raimund Seidel, Erstgutachter Prof, ...
We investigate the performance of exact algorithms for hard optimization problems under random inputs. In particular, we prove various structural properties that lead to two general average-case...
A better upper bound on the number of triangulations of a planar point set (2002)
Santos, Francisco, Seidel, Raimund
We show that a point set of cardinality $n$ in the plane cannot be the vertex set of more than $59^n O(n^{-6})$ straight-edge triangulations of its convex hull. This improves the previous upper bound...
Maximizing a Vo24 Regio The Co vex Case Frank Dehne (2002)
Klein And Rdo, Frank Dehne, Rolf Klein, Raimund Seidel
Given a set S o s po7 ts in the plane, wheredo we place a new poK t, p, ino77) to maximize the areao itsregio in the Vo9730 diagramo S and p? We study the case where the Vo80(8 neighbo9 o p are in co...
Checking geometric programs or verification of geometric structures (1999)
Mehlhorn, Kurt, Näher, Stefan, Seel, Michael, Seidel, Raimund, Schilz, Thomas, Schirra, Stefan, ...
Results on k-sets and j-facets via continuous motion (1998)
Artur Andrzejak, Boris Aronov, Sariel Har-peled, Raimund Seidel, Emo Welzl
Let P be a set of n points in IR
On the exact worst case query complexity of planar point location (1998)
What is the smallest constant c so that the planar point location queries can be answered in c log 2 n + o(log n) steps (i.e. point-line comparisons) in the worst case? In SODA 97 Goodrich, Orletsky,...
On the exact worst case query complexity of planar point location (1998)
What is the smallest constant c so that the planar point location queries can be answered in c log 2 n + o(log n) steps (i.e. point-line comparisons) in the worst case? Goodrich, Orletsky, and...
Efficient perturbations for handling geometric degeneracies (1997)
Ioannis Z. Emiris, John F. Canny, Raimund Seidel
This article de nes input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is proposed...
How good are convex hull algorithms (1997)
David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
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...
Efficient perturbations for handling geometric degeneracies (1997)
Ioannis Z. Emiris, John F. Canny, Raimund Seidel
Abstract. This article defines input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is...
Rolf Klein, Raimund Seidel, Seth Teller, Rolf Klein (hagen, Raimund Seidel (saarbrucken
This report contains the abstracts of all the 29 talks, in the order as they were given at the meeting, as well as abstracts of the problems presented at the open problem session. Compiled by Rolf...
Efficient Perturbations for Handling Geometric Degeneracies (1997)
Ioannis Z. Emiris, John F. Canny, Raimund Seidel
. This article defines input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is...
How Good are Convex Hull Algorithms? (1997)
David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
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...
Efficient Perturbations for Handling Geometric Degeneracies (1997)
Ioannis Z. Emiris, John F. Canny, Raimund Seidel
. This article defines input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is...
School Of, David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
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...
Results on k-Sets and j-Facets via Continuous Motion (1997)
Artur Andrzejak, Boris Aronov, Sariel Har-peled, Raimund Seidel, Emo Welzl
Let P be a set of n points in IR d in general position, i.e., no i + 1 points on a common (i \Gamma 1)-flat, 1 i d. A k-set of P is a set S of k points in P that can be separated from P nS by a...
Checking geometric programs or verification of geometric structures (1996)
Kurt Mehlhorn, Stefan Naher, Michael Seel, Raimund Seidel, Thomas Schilz, Stefan Schirra, ...
A program checker verifies that a particular program execution is correct. We give simple and efficient program checkers for some basic geometric tasks. We report about our experiences with program...
Errata: Better Lower Bounds on Detecting Affine and Spherical Degeneracies (1996)
Jeff Erickson, Raimund Seidel, Fachbereich Informaik
disjoint from every other surface induced by \Phi. The correctness of the perturbation technique is based on the following incorrect claim [1, p.48]: Let C be an arbitrary cell, and let C 0 be one of...
Checking Geometric Programs or Verification of Geometric Structures (1996)
Kurt Mehlhorn Stefan, Stefan Näher, Michael Seel, Raimund Seidel, Thomas Schilz, Stefan Schirra, ...
A program checker verifies that a particular program execution is correct. We give simple and efficient program checkers for some basic geometric tasks. We report about our experiences with program...
Checking Geometric Programs or Verification of Geometric Structures (1996)
Mehlhorn, Kurt, Näher, Stefan, Schilz, Thomas, Schirra, Stefan, Seel, Michael, Seidel, Raimund, ...
Better Lower Bounds on Detecting Affine and Spherical Degeneracies (1995)
Jeff Erickson Computer, Je Erickson, Raimund Seidel, Fachbereich Informaik
d is either completely contained in or completely disjointfromevery other surface induced by\Phi. The correctness of the perturbation technique is based on the following incorrect claim [1, p.48]:...
Better Lower Bounds on Detecting Affine and Spherical Degeneracies (1995)
We show that in the worst case,\Omega (n d ) sidedness queries are required to determine whether a set of n points in IR d is affinely degenerate, i.e., whether it contains d +1points on a common...
Better Lower Bounds on Detecting Affine and Spherical Degeneracies (1995)
We show that in the worst case,\Omega\Gamma n d ) sidedness queries are required to determine whether a set of n points in IR d is affinely degenerate, i.e., whether it contains d + 1 points on a...
On Compatible Triangulations of Simple Polygons (1993)
Boris Aronov, Raimund Seidel, Diane Souvaine
It is well known that, given two simple n-sided polygons, it may not be possible to triangulate the two polygons in a compatible fashion, if one's choice of triangulation vertices is restricted...
On the all-pairs-shortest-path problem (1992)
The following algorithm solves the distance version of the all-pairs-shortest-path problem for undirected, unweighed n-vertex graphs in time O(&f(rJ) log n), where M(n) denotes the time necessary...
Backwards Analysis of Randomized Geometric Algorithms (1992)
The theme of this paper is a rather simple method that has proved very potent in the analysis of the expected performance of various randomized algorithms and data structures in computational...
Arrangements of curves in the plane --- topology, combinatorics, and algorithms. (1992)
Edelsbrunner, Herbert, Guibas, Leonidas, Pach, János, Pollack, Richard, Seidel, Raimund, Sharir, Micha
Four Results on Randomized Incremental Constructions (1992)
Clarkson, Kenneth L., Mehlhorn, Kurt, Seidel, Raimund, Finkel, Alain, Jantzen, Matthias
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...
Elsevier Counting and cutting cycles of lines and rods in space* (1991)
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, ...
306 B. Chazelle et al.
How to net a lot with little: small "-nets for disks and halfspaces (1990)
It is known that in general range spaces of VC-dimension d? 1 require "-nets to be of size at least\Omega\Gamma d " log 1 "). We address the question whether this general...
Randomized search trees (1989)
Raimund Seidel, Fachberich Informatik, Cecilia R. Aragon
We present a randomized strategy for maintaining balance in dynamically changing search trees that has optimal expected behavior. In particular, in the expected case a search or an update takes...
Output-Size Sensitive Algorithms for Constructive Problems in Computational Geometry (1986)
In computer science the efficiency of algorithms is usually measured in terms of the size of the input. The output size, on the other hand, has been used for this purpose rather infrequently, except...
Output-Size Sensitive Algorithms for Constructive Problems in Computational Geometry (1986)
In computer science the efficiency of algorithms is usually measured in terms of the size of the input. The output size, on the other hand, has been used for this purpose rather infrequently, except...
Output-size sensitive algorithms for constructive problems in computational geometry / (1986)
Includes bibliographical references (p. [135]-138).
Thesis (Ph. D.)--Cornell University, 1987.
Voronoi Diagrams and Arrangements (1985)
Edelsbrunner, Herbert, Seidel, Raimund
We propose a uniform and general framework for defining and dealing with Voronoi Diagrams. In this framework a Voronoi Diagram is a partition of a domain $D$ induced by a finite number of real valued...
Voronoi Diagrams and Arrangements (1985)
Edelsbrunner, Herbert, Seidel, Raimund
We propose a uniform and general framework for defining and dealing with Voronoi Diagrams. In this framework a Voronoi Diagram is a partition of a domain $D$ induced by a finite number of real valued...
A Method for Proving Lower Bounds for Certain Geometric Problems (1984)
We prove lower bounds for a number of geometric problems. Our results show that certain types of additional input information cannot possibly permit faster solutions for these problems. The main idea...
A Method for Proving Lower Bounds for Certain Geometric Problems (1984)
We prove lower bounds for a number of geometric problems. Our results show that certain types of additional input information cannot possibly permit faster solutions for these problems. The main idea...
The Ultimate Planar Convex Hull Algorithm ? (1983)
Kirkpatrick, David G., Seidel, Raimund
We present a new planar convex hull algorithm with worst case time complexity $O(n \log H)$ where $n$ is the size of the input set and $H$ is the size of the output set, i.e. the number of vertices...
The Ultimate Planar Convex Hull Algorithm ? (1983)
Kirkpatrick, David G., Seidel, Raimund
We present a new planar convex hull algorithm with worst case time complexity $O(n \log H)$ where $n$ is the size of the input set and $H$ is the size of the output set, i.e. the number of vertices...
A convex hull algorithm optimal for point sets in even dimensions [microform] / (1983)
Thesis (M. Sc.)--University of British Columbia, 1981.