On the Stretch Factor of Convex Delaunay Graphs (2010)
Prosenjit Bose, Paz Carmi, Sébastien Collette, Michiel Smid
Abstract. Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DGC(S) of S is defined to be...
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [12]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
Pi/2-Angle Yao Graphs are Spanners (2010)
Bose, Prosenjit, Damian, Mirela, Douieb, Karim, O'Rourke, Joseph, Seamone, Ben, Smid, Michiel, ...
We show that the Yao graph Y4 in the L2 metric is a spanner with stretch factor 8(29+23sqrt(2)). Enroute to this, we also show that the Yao graph Y4 in the Linf metric is a planar spanner with...
ALGORITHMS FOR MARKETING-MIX OPTIMIZATION (2010)
Joachim Gudmundsson, Pat Morin, Michiel Smid
Abstract. Algorithms for determining quality/cost/price tradeoffs in saturated markets are considered. A product is modeled by d real-valued qualities whose sum determines the unit cost of producing...
Das, Gautam, Gudmundsson, Joachim, Klein, Rolf, Knauer, Christian, Smid, Michiel
From November 1 to 6, 2009, the Dagstuhl Seminar 09451 ``Geometric Networks, Metric Space Embeddings and Spatial Data Mining'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During...
On the falsepositive rate of Bloom filters (2009)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
Abstract Rotationally Monotone Polygons ∗ (2009)
Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
A generalization of monotonicity is introduced. An nvertex polygon P is rotationally monotone w.r.t. a point r if there exists a partitioning of the boundary of P into exactly two polygonal chains,...
An Ω lower bound for computing the sum of even-ranked elements (2009)
Mörig, Marc, Rautenbach, Dieter, Smid, Michiel, Tusch, Jan
Preprint / Technische Universität Ilmenau, Institut für Mathematik ; 09-16
Algorithms for Marketing-Mix Optimization (2009)
Gudmundsson, Joachim, Morin, Pat, Smid, Michiel
Algorithms for determining quality/cost/price tradeoffs in saturated markets are considered. A product is modeled by $d$ real-valued qualities whose sum determines the unit cost of producing the...
Jörg Schwerdt, Michiel Smid, Man Chung Hon, Ravi Janardan
In Layered Manufacturing (LM), a prototype of a virtual polyhedral object is built by slicing the object into polygonal layers, and then building the layers one after another. In StereoLithography, a...
An \Omega(n log n) lower bound for computing the sum of even-ranked elements (2009)
Mörig, Marc, Rautenbach, Dieter, Smid, Michiel, Tusch, Jan
Given a sequence A of 2n real numbers, the Even-Rank-Sum problem asks for the sum of the n values that are at the even positions in the sorted order of the elements in A. We prove that, in the...
Algorithms for Designing Clamshell Molds (2008)
Stefanie Wuhrer, Prosenjit Bose, Pat Morin, Michiel Smid
Clamshell casting is a popular manufacturing technique where liquid is poured into a mold or cast and the cast is removed once the liquid has hardened. The term clamshell refers to the way in which...
Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...
A Linear-Space Algorithm for Distance Preserving Graph Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in d-dimensional Euclidean space for a constant d so that for each edge the distance between...
Indicator Random Variables in Traffic Analysis and the Birthday Problem (2008)
Phillip G. Bradford, Irina Perevalova, Michiel Smid, Charles B. Ward
Abstract This paper proposes using collisions of Pareto randomvariables in traffic analysis and in generating fictitious network traffic that follows various Pareto distributions.Pareto distributions...
Communication-Efficient Construction of the Plane Localized Delaunay Graph (2008)
Bose, Prosenjit, Carmi, Paz, Smid, Michiel, Xu, Daming
Let $V$ be a finite set of points in the plane. We present a 2-local algorithm that constructs a plane $\frac{4 \pi \sqrt{3}}{9}$-spanner of the unit-disk graph $\UDG(V)$. This algorithm makes only...
Joachim Gudmundsson, Michiel Smid
Constructing plane spanners of bounded degree and low weight
Indicator Random Variables in Traffic Analysis and the Birthday Problem (2008)
Phillip G. Bradford, Irina Perevalova, Michiel Smid, Charles B. Ward
This paper proposes using collisions of Pareto random variables in traffic analysis and in generating fictitious network traffic that follows various Pareto distributions. Pareto distributions are...
Sparse geometric graphs with small dilation (2008)
Aronov, Boris, De Berg, Mark, Cheong, Otfried, Gudmundsson, Joachim, Haverkort, Herman, Smid, Michiel, ...
Given a set S of n points in , and an integer k such that 0k
On the Stretch Factor of Convex Delaunay Graphs (2008)
Bose, Prosenjit, Carmi, Paz, Collette, Sebastien, Smid, Michiel
Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DG_C(S) of S is defined to be the dual of...
Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...
Heuristics for Estimating Contact-Area of Supports in Layered Manufacturing (2008)
Ivaylo Ilinkin, Ravi Janardan, Michiel Smid, Eric Johnson, Paul Castillo, Jörg Schwerdt
Layered Manufacturing is a technology that allows physical prototypes of three-dimensional models to be built directly from their digital representation, as a stack of two-dimensional layers. A key...
ALGORITHMS FOR OPTIMAL OUTLIER REMOVAL ∗ (2008)
Rossen Atanassov, Prosenjit Bose, Mathieu Couture, Anil Maheshwari, Pat Morin, Michel Paquette, ...
Abstract. We consider the problem of removing c points from a set S of n points so that the remaining point set is optimal in some sense. Definitions of optimality we consider include having minimum...
On Generalized Diamond Spanners (2008)
Prosenjit Bose, Aaron Lee, Michiel Smid
Given a set P of points in the plane and a set L of non-crossing line segments whose endpoints are in P, a constrained plane geometric graph is a plane graph whose vertex set is P and whose edge set...
Computing Large Planar Regions in Terrains Abstract (2008)
Katharina Lange, Rahul Ray, Michiel Smid, Ulrich Wendt
We consider the problem of computing the largest region in a terrain that is approximately contained in some two-dimensional plane. We reduce this problem to the following one. Given an embedding of...
Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel Smid
Abstract. Let G be a graph embedded in Euclidean space. For any two vertices of G their dilation denotes the length of a shortest connecting path in G, divided by their Euclidean distance. In this...
On the falsepositive rate of Bloom filters (2008)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
Efficient Construction of a Bounded Degree Spanner (2008)
Low Weight, Sunil Arya, Michiel Smid
Let S be a set of n points in IR d and let t> 1 be a real number. A t-spanner for S is a graph having the points of S as its vertices such that for any pair p,q of points there is a path between...
Prosenjit Gupta, Ravi Janardan, Michiel Smid, Bhaskar Dasgupta
rectangle enclosure and point{dominance problems revisited
Abstract Sigma-Local Graphs (2008)
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [9]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
Communicated by Joseph S.B. Mitchell Geometric intersection searching problems are a well-studied class of query-retrieval problems with many applications. The goal here is to preprocess a set of...
Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed by a rotation once the liquid has hardened. We consider the case where the object to...
Abstract Sigma-Local Graphs (2008)
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [11]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
Space-Efficient Geometric Divide-and-Conquer Algorithms ⋆ Prosenjit Bose a Anil Maheshwari a (2008)
Pat Morin A, Jason Morrison, Michiel Smid, Jan Vahrenhold
We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth...
Anil Maheshwari, Pat Morin, Michel Paquette, Michiel Smid, Stefanie Wuhrer
We consider the problem of removing c points from a set S of n points so that the remaining point set is optimal in some sense. Definitions of optimality we consider include having minimum diameter,...
Space-Efficient Geometric Divide-and-Conquer Algorithms ⋆ Prosenjit Bose a Anil Maheshwari a (2008)
Pat Morin A, Jason Morrison, Michiel Smid, Jan Vahrenhold
We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth...
Nordic Journal of Computing RANGE MODE AND RANGE MEDIAN QUERIES ON LISTS AND TREES ∗ (2008)
Danny Krizanc, Pat Morin, Michiel Smid
Abstract. We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of...
The Gap Property in Doubling Metrics (2008)
We introduce the weak gap property as a variant of the gap property. We show that in any metric space of bounded doubling dimension, any directed graph whose vertex set S has size n and which...
Spanners of Complete $k$-Partite Geometric Graphs (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Morin, Pat, Smid, Michiel
We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in $\mathbb{R}^d$, compute a spanner of $K$ that has a ``small'' stretch...
Fault-Tolerant Spanners (2007)
Christos Levcopoulos, Giri Narasimhan, And Michiel Smid, Michiel Smid
tolerance. Next, we give an alternate construction of a network G = (S; E), based on well-separated pairs, such that for any set E 0 ae E of size at most k, and any pair of vertices, x; y 2 S, the...
On the falsepositive rate of Bloom filters (2007)
Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, ...
Abstract. Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed...
Sunil Arya, David M. Mount, Michiel Smid
Randomized and deterministic algorithms for geometric spanners of small diameter
A Decomposition-Based Approach to Layered (2007)
Ivaylo Ilinkin, Ravi Janardan, Jayanth Majhi, Michiel Smid, Ram Sriram
This paper introduces a new approach for improving the performance and versatility of Layered Manufacturing (LM), which is an emerging technology that makes it possible to build physical prototypes...
Light Edges in Degree-Constrained Graphs Prosenjit Bose z (2007)
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
THE RECONSTRUCTION OF DYNAMIC DATA STRUCTURES (2007)
Michiel Smid, Mark Overmars, Vakgroep Informatica, Michiel H. M. Smid, Leen Torenvliet, Leen Torenvliet, ...
dynamic data structures
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid
Given a geometric t-spanner graph G in E d with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. Then, after O(m+n log n) preprocessing, we present an...
This LEP is based on the rst author's Master's Thesis [9]. y (2007)
Jrg Schwerdt, Michiel Smid, Stefan Schirra, Fakultt Fr Informatik, Otto-von-guericke-universitt Magdeburg
This LEDA extension package solves the optimization problem that we call diameter problem for moving points and that is dened as follows. Denition 1.1 Let p be a point in the plane that is moving at...
Jorg Schwerdt, Michiel Smid, Man Chung Hon, Ravi Janardan
In Layered Manufacturing (LM), a prototype of a virtual polyhedral object is built by slicing the object into polygonal layers, and then building the layers one after another. In StereoLithography, a...
Sunil Arya, David M. Mount, Michiel Smid
Randomized and deterministic algorithms for geometric spanners of small diameter
Light Edges in Degree-Constrained Graphs (2007)
Prosenjit Bose Michiel, Michiel Smid, David R. Wood
Let denote the average degree, and denote the minimum degree of a graph.
Approximating Geometric Bottleneck Shortest Paths (2007)
Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh
In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L,...
Geometric Spanners With Small Chromatic Number (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Maheshwari, Anil, Smid, Michiel, Zeh, Norbert
Given an integer $k \geq 2$, we consider the problem of computing the smallest real number $t(k)$ such that for each set $P$ of points in the plane, there exists a $t(k)$-spanner for $P$ that has...
On a family of strong geometric spanners that admit local routing strategies (2007)
Bose, Prosenjit, Carmi, Paz, Couture, Mathieu, Smid, Michiel, Xu, Daming
We introduce a family of directed geometric graphs, denoted $\paz$, that depend on two parameters $\lambda$ and $\theta$. For $0\leq \theta
Sparse geometric graphs with small dilation (2007)
Aronov, Boris, De Berg, Mark, Cheong, Otfried, Gudmundsson, Joachim, Haverkort, Herman, Smid, Michiel, ...
Given a set S of n points in R^D, and an integer k such that 0
Geometric spanners with small chromatic number (2007)
Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel Smid, Norbert Zeh
Abstract. Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, there exists a t(k)-spanner for P that has...
Dilation-optimal edge deletion in polygonal cycles (2007)
Hee-kap Ahn, Mohammad Farshi, Christian Knauer, Michiel Smid, Yajun Wang
Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them....
Rotationally Monotone Polygons, Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
doi:10.1016/j.comgeo.2007.02.004 www.elsevier.com/locate/comgeo We introduce a generalization of monotonicity. An n-vertex polygon P is rotationally monotone with respect to a point r if there exists...
Geometric Spanners With (2007)
Small Chromatic Number, Anil Maheshwari, Michiel Smid, Norbert Zeh
Given an integer k ≥ 2, we consider the problem of computing the smallest real number t(k) such that for each set P of points in the plane, a t(k)-spanner for P exists that has O(|P |) edges and...
Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu
a family of strong geometric spanners that admit local
Spanners of Complete k-Partite Geometric Graphs Prosenjit Bose ∗ Paz Carmi ∗ Mathieu Couture (2007)
Anil Maheshwari Pat Morin, Michiel Smid
We address the following problem: Given a complete k-partite geometric graph K whose vertex set is a set of n points in R d, compute a spanner of K that has a “small ” stretch factor and “few...
06481 Abstracts Collection -- Geometric Networks and Metric Space Embeddings (2007)
Gudmundsson, Joachim, Klein, Rolf, Narasimhan, Giri, Smid, Michiel, Wolff, Alexander
The Dagstuhl Seminar 06481 ``Geometric Networks and Metric Space Embeddings'' was held from November~26 to December~1, 2006 in the International Conference and Research Center (IBFI), Schloss...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Higman’s Theorem in Formal Languages (2006)
Let Σ be a finite alphabet. For any two strings x and y in Σ ∗ , we say that x is a subsequence of y, if x can be obtained by deleting zero or more symbols from y. For example, 10110 is a...
On spanners of geometric graphs (2006)
Joachim Gudmundsson, Michiel Smid
Given a connected geometric graph G, we consider the problem of constructing a t-spanner of G having the minimum number of edges. We prove that for every t with 1 < t < 1 log n, there exists a...
Rotational clamshell casting in two dimensions (2006)
Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed once the liquid has hardened. We consider the case where the object to be...
Rotational clamshell casting in three dimensions (2006)
Prosenjit Bose, Pat Morin, Michiel Smid, Stefanie Wuhrer
A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed once the liquid has hardened. We consider the case where the object to be...
Geometric Networks and Metric Space Embeddings (2006)
Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, Alexander Wolff, Tu Eindhoven, ...
Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. In this paper we describe the seminar topics, we have compiled...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, John Iacono, Stefan Langerman, Michiel Smid
Abstract. We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, John Iacono, Stefan Langerman, Michiel Smid
Abstract. We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line...
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams (2005)
Aronov, Boris, Bose, Prosenjit, Demaine, Erik D., Gudmundsson, Joachim, Iacono, John, Langerman, Stefan, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line l in the...
Fast pruning of geometric spanners (2005)
Joachim Gudmundsson, Giri Narasimhan, Michiel Smid
Abstract. Let S be a set of points in R d. Given a geometric spanner graph, G = (S, E), with constant dilation t, and a positive constant ε, we show how to construct a (1 + ε)-spanner of G with...
Sparse geometric graphs with small dilation (2005)
Boris Aronov, Mark Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, ...
Given a set S of n points in R D, and an integer k such that 0 � k < n, we show that a geometric graph with vertex set S, at most n − 1 + k edges, maximum degree five, and dilation O(n/(k +...
Sparse geometric graphs with small dilation (2005)
Boris Aronov, Mark De Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, ...
Abstract. Given a set S of n points in R D, and an integer k such that 0 � k < n, we show that a geometric graph with vertex set S, at most n − 1 + k edges, maximum degree five, and dilation...
Rolf Klein, Christian Knauer, Giri Narasimhan, Michiel Smid
Let G be a graph embedded in Euclidean space. For any two vertices of G their dilation denotes the length of a shortest connecting path in G, divided by their Euclidean distance. In this paper we...
Computing Large Planar Regions in Terrains, with an Application to Fracture Surface (2004)
Smid,Michiel, Ray,Rahul, Wendt,Ulrich, Lange,Katharina
We consider the problem of computing the largest region in a terrain that is approximately contained in some two-dimensional plane. We reduce this problem to the following one. Given an embedding of...
Computing Large Planar Regions in Terrains, with an Application to Fracture Surface (2004)
Smid, Michiel, Ray, Rahul, Wendt, Ulrich, Lange, Katharina
We consider the problem of computing the largest region in a terrain that is approximately contained in some two-dimensional plane. We reduce this problem to the following one. Given an embedding of...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
Let denote the average degree, and denote the minimum degree of a graph. An edge is light if both its endpoints have degree bounded by a constant depending only on and. A graph is degree-constrained...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
Light edges in degree-constrained graphs (2004)
Prosenjit Bose, Michiel Smid, David R. Wood
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
Light Edges in Degree-Constrained Graphs (2004)
Prosenjit Bose Michiel, Michiel Smid, David R. Wood
A graph whose average degree is less than twice the minimum degree is called degree-constrained. An edge of a graph with bounded degree end-points is said to be light. The primary result of this...
Approximating Geometric Bottleneck Shortest Paths (2004)
Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, Norbert Zeh
In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L,...
Computing Large Planar Regions in Terrains, with an Application to Fracture Surface (2004)
Smid, Michiel, Ray, Rahul, Wendt, Ulrich, Lange, Katharina
We consider the problem of computing the largest region in a terrain that is approximately contained in some two-dimensional plane. We reduce this problem to the following one. Given an embedding of...
Range Mode and Range Median Queries on Lists and Trees (2003)
Krizanc, Danny, Morin, Pat, Smid, Michiel
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Range mode and range median queries on lists and trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
ABSTRACT. We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of...
Range Mode and Range Median Queries on Lists and Trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Primality Testing in Polynomial Time (2003)
These notes contain a description and correctness proof of the deterministic polynomial-time primality testing algorithm of Agrawal, Kayal, and Saxena. Some background from number theory and algebra...
Range Mode and Range Median Queries on Lists and Trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Range Mode And Range Median Queries On Lists And Trees (2003)
Danny Krizanc Wesleyan, Danny Krizanc, Pat Morin, Michiel Smid
We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on...
Range mode and range median queries on lists and trees (2003)
Danny Krizanc, Pat Morin, Michiel Smid
Abstract. We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of...
Distance-preserving approximations of polygonal paths (2003)
Joachim Gudmundsson, Giri Narasimhan, Michiel Smid
Given a polygonal path P with vertices p1, p2,..., pn ∈ Rd and a real number t ≥ 1, a path Q = (pi1, pi2,..., pik) is a t-distance-preserving approximation of P if 1 = i1 < i2 <... < ik...
Translating a Planar Object to Maximize Point Containment (2002)
Agarwal,Pankaj, Hagerup,Torben, Ray,Rahul, Sharir,Micha, Smid,Michiel, Welzl,Emo
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points...
Surface Topography Quantification by Integral and Feature-related Parameters (2002)
Wendt,Ulrich, Lange,Katharina, Smid,Michiel, Ray,Rahul, Tönnies,Klaus-Dietz
Using topographical images obtained by confocal laser scanning microscopy, the topography of brittle fracture surfaces and wire-eroded surfaces was quantified. The global topometry values show a...
Computing Large Planar Regions in Terrains (2002)
Ray,Rahul, Smid,MIchiel, Lange,Katharina, Wendt,Ulrich
We consider the problem of computing the largest region in a terrain that is approximately contained in some two-dimensional plane. We reduce this problem to the following one. Given an embedding of...
Translating a Planar Object to Maximize Point Containment (2002)
Agarwal, Pankaj, Hagerup, Torben, Ray, Rahul, Sharir, Micha, Smid, Michiel, Welzl, Emo, ...
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points...
Surface Topography Quantification by Integral and Feature-related Parameters (2002)
Wendt, Ulrich, Lange, Katharina, Smid, Michiel, Ray, Rahul, Tönnies, Klaus-Dietz
Using topographical images obtained by confocal laser scanning microscopy, the topography of brittle fracture surfaces and wire-eroded surfaces was quantified. The global topometry values show a...
Computing Large Planar Regions in Terrains (2002)
Ray, Rahul, Smid, MIchiel, Lange, Katharina, Wendt, Ulrich, Fourey, Sébastien, Herman, Gabor T., ...
We consider the problem of computing the largest region in a terrain that is approximately contained in some two-dimensional plane. We reduce this problem to the following one. Given an embedding of...
Translating a planar object to maximize point containment (2002)
Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl
Abstract. Let C be a compact set in R
Constructing plane spanners of bounded degree and low weight (2002)
Joachim Gudmundsson, Michiel Smid
Given a set S of n points in the plane, we give an O(n log n)-time algorithm that constructs a plane t-spanner for S, for t 10:02, such that the degree of each point of S is bounded from above by 27,...
Improved algorithms for constructing fault-tolerant spanners (2002)
Christos Levcopoulos, Giri Narasimhan, Michiel Smid
Let S be a set of n points in a metric space, and k a positive integer. Algorithms are given that construct k-fault-tolerant spanners for S. If in such a spanner at most k vertices and/or edges are...
Approximation algorithms for the bottleneck stretch factor problem (2002)
The stretch factor of a Euclidean graph is the maximum ratio of the distance in the graph between any two points and their Euclidean distance. Given a set S of n points in R d, we show how to...
Improved algorithms for constructing fault-tolerant spanners (2002)
Christos Levcopoulos, Giri Narasimhan, Michiel Smid
Let S be a set of n points in a metric space, and k a positive integer. Algorithms are given that construct k-fault-tolerant spanners for S. If in such a spanner at most k vertices and/or edges are...
Approximation algorithms for the bottleneck stretch factor problem (2002)
The stretch factor of a Euclidean graph is the maximum ratio of the distance in the graph between any two points and their Euclidean distance. Given a set S of n points in Rd, we show how to...
Translating a planar object to maximize point containment (2002)
Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl
Abstract. Let � be a compact set in Ê and let Ë beasetofÒpoints in Ê.We consider the problem of computing a translate of � that contains the maximum number, � £ , of points of Ë. It is...
Approximate Distance Oracles Revisited (2002)
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid
Let G be a geometric t-spanner in E with n points and m edges, where t is a constant. We show that G can be preprocessed in O(m log n) time, such that (1+")-approximate shortest-path queries in...
I/O-efficient shortest path queries in geometric spanners (2001)
Abstract. We present I/O-efficient algorithms to construct planar Steiner spanners for point sets and sets of polygonal obstacles in the plane, and for constructing the “dumbbell ” spanner of [6]...
I/O-efficient shortest path queries in geometric spanners (2001)
Abstract. We present I/O-efficient algorithms to construct planar Steiner spanners for point sets and sets of polygonal obstacles in the plane, and for constructing the “dumbbell ” spanner of [6]...
Approximating the stretch factor of euclidean graphs (2000)
Given a set S of n points in R d, and a graph G having the points of S as its vertices, the stretch factor t of G is dened as the maximal value jpqj G =jpqj, where p; q 2 S, p 6 = q, jpqj G is the...
Protecting critical facets in layered manufacturing (2000)
Michiel Smid, Ravi Janardan, Eric Johnson
In Layered Manufacturing, a three-dimensional polyhedral object is built by slicing its (virtual) CAD model, and manufacturing the slices successively. During this process, support structures are...
Protecting Critical Facets in Layered Manufacturing: Implementation and Experimental Results (2000)
Jörg Schwerdt, Michiel Smid, Ravi Janardan, Eric Johnson
In Layered Manufacturing, a three-dimensional polyhedral object is built by slicing its (virtual) CAD model, and manufacturing the slices successively. During this process, support structures are...
Approximating The Stretch Factor Of Euclidean Graphs (2000)
. There are several results available in the literature dealing with ecient construction of t-spanners for a given set S of n points in R d . t-spanners are Euclidean graphs in which distances...
Approximation algorithms for the bottleneck stretch factor problem
Approximating the stretch factor of euclidean graphs (2000)
Abstract. There are several results available in the literature dealing with efficient construction of t-spanners for a given set S of n points in R d. t-spanners are Euclidean graphs in which...
Linear Programming: The Ellipsoid Algorithm (1999)
Introduction This chapter is based on the books [1, 2, 4]. Denition 1 (LP) Linear Programming is the following problem: Given an m n matrix A = (a ij ), an m-vector b = (b 1 ; : : : ; b m ) T , and...
to the sorting problem. First note that many sorting algorithms, such as insertion-sort, merge-sort, heapsort, and quicksort, are comparison based. Fakultat fur Informatik,...
Improved Algorithms for Constructing Fault-Tolerant Spanners (1999)
Christos Levcopoulos, Giri Narasimhan, Michiel Smid
Let S be a set of n points in a metric space, and k a positive integer. Algorithms are given that construct k-fault-tolerant spanners for S. If in such a spanner at most k vertices and/or edges are...
Skip Lists: A Randomized Dictionary (1999)
Introduction We consider the dictionary problem: Given a set S of n real numbers, store them in a data structure such that the following three operations can be performed eciently: 1. Search(x):...
Implementing Dictionaries Using Hashing (1999)
Introduction This chapter is based on Mehlhorn [5]. Many algorithms manipulate sets. For example, a compiler uses a symbol table to keep track of the identifiers that are used in a program....
Approximating the stretch factor of Euclidean graphs (1999)
Given a set S of n points in R d , and a connected graph G having the points of S as its vertices, the stretch factor t of G is dened as the maximal value jpqj G =jpqj, where p; q 2 S, p 6= q, jpqj G...
A Lower Bound for Approximating the Geometric Minimum Weight Matching (1999)
Given a set S of 2n points in R d , a perfect matching of S is a set of n edges such that each point of S is a vertex of exactly one edge. The weight of a perfect matching is the sum of the Euclidean...
Approximating the stretch factor of Euclidean paths, cycles and trees (1999)
Given a set S of n points in R d , and a graph G having the points of S as its vertices, the stretch factor t of G is defined as the maximal value jpqj G =jpqj, where p; q 2 S, p 6= q, jpqj G is the...
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions (1999)
Sunil Arya, David M. Mount, Michiel Smid
Let S be a set of n points in IR d and let t> 1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a...
Randomized data structures for the dynamic closest-pair problem (1998)
Golin, Mordecai J., Raman, Rajeev, Schwarz, Christian, Smid, Michiel
We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional...
Computing the Width of a Three-Dimensional Point Set: An Experimental Study (1998)
Jörg Schwerdt, Michiel Smid, Jayanth Majhi, Ravi Janardan
We describe a robust, exact, and efficient implementation of an algorithm that computes the width of a three-dimensional point set. The algorithm is based on efficient solutions to problems that are...
Computing the Width of a Three-Dimensional Point Set: An Experimental Study (1998)
Jörg Schwerdt, Michiel Smid, Jayanth Majhi, Ravi Janardan
We describe a robust, exact, and efficient implementation of an algorithm that computes the width of a three-dimensional point set. The algorithm is based on efficient solutions to problems that are...
Selected Topics in Data Structures (1998)
Michiel Smid, K. Mehlhorn, S. Naher, Dynamic Algorithmica
Introduction through Randomized Algorithms. Prentice Hall, Englewood Cliffs, 1994. [17] M.H. Overmars. The Design of Dynamic Data Structures. Lecture Notes in Computer Science, Vol. 156,...
Computing the Width of a Three-Dimensional Point Set: An Experimental Study (1998)
Jörg Schwerdt, Michiel Smid, Jayanth Majhi, Ravi Janardan
We describe a robust, exact, and efficient implementation of an algorithm that computes the width of a three-dimensional point set. The algorithm is based on efficient solutions to problems that are...
Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners (1998)
Christos Levcopoulos, Giri Narasimhan, Michiel Smid
Let S be a set of n points in IR d , and k an integer such that 1 k n \Gamma 2. Algorithms are given that construct fault-tolerant spanners for S. If in such a spanner at most k edges or vertices are...
Minimizing Support Structures and Trapped Area in Two-Dimensional Layered Manufacturing (1998)
Jayanth Majhi, Ravi Janardan, Jörg Schwerdt, Michiel Smid, Prosenjit Gupta
Efficient geometric algorithms are given for the two-dimensional versions of optimization problems arising in layered manufacturing, where a polygonal object is built by slicing its CAD model and...
Algorithms for Some Intersection Searching Problems Involving Circular Objects (1998)
Prosenjit Gupta, Ravi Janardan, Michiel Smid
Two classes of geometric intersection searching problems are considered, i.e., problems in which a set S of geometric objects is to be preprocessed into a data structure so that for any query object...
On some geometric optimization problems in layered manufacturing (1997)
Jayanth Majhi, Ravi Janardan, Michiel Smid
In Layered Manufacturing, the choice of the build direction for the model in uences several design criteria, including the number of layers, the volume and contact-area of the support structures, and...
Gautam Das Sanjiv, Gautam Das, Sanjiv Kapoor, Michiel Smid
We consider the problems of computing r-approximate traveling salesman tours and r-approximate minimum spanning trees for a set of n points in IR d , where d 1 is a constant. In the algebraic...
Gautam Das Sanjiv, Gautam Das, Sanjiv Kapoor, Michiel Smid
We consider the problems of computing r-approximate traveling salesman tours and r-approximate minimum spanning trees for a set of n points in IR d , where d 1 is a constant. In the algebraic...
Minimizing Support Structures and Trapped Area in Two-Dimensional Layered Manufacturing (1997)
Jayanth Majhi, Ravi Janardan, Jorg Schwerdt, Michiel Smid, Prosenjit Gupta
Efficient geometric algorithms are given for the two-dimensional versions of optimization problems arising in layered manufacturing, where a polygonal object is built by slicing its CAD model and...
On Some Geometric Optimization Problems in Layered Manufacturing (1997)
Jayanth Majhi Ravi, Ravi Janardan, Michiel Smid, Prosenjit Gupta
Efficient geometric algorithms are given for optimization problems arising in layered manufacturing, where a 3D object is built by slicing its CAD model into layers and manufacturing the layers...
On Some Geometric Optimization Problems in Layered Manufacturing (Extended Abstract) (1997)
Jayanth Majhi, Ravi Janardan, Michiel Smid, Prosenjit Gupta
) Jayanth Majhi Ravi Janardan Michiel Smid y Prosenjit Gupta z 1 Introduction This paper describes efficient algorithms for certain geometric optimization problems arising in layered manufacturing....
Multi-criteria geometric optimization problems in Layered Manufacturing (Extended Abstract) (1997)
J. Majhi, Jayanth Majhi, Ravi Janardan, Michiel Smid, Jorg Schwerdt
) Jayanth Majhi Ravi Janardan Michiel Smid y Jorg Schwerdt y 1 Introduction Layered Manufacturing (LM) is an exciting new technology which enables complex 3D parts to be built directly from their CAD...
Closest-Point Problems in Computational Geometry (1997)
This is the preliminary version of a chapter that will appear in the Handbook on Computational Geometry, edited by J.-R. Sack and J. Urrutia. A comprehensive overview is given of algorithms and data...
Multi-criteria geometric optimization problems in Layered Manufacturing (1997)
Jayanth Majhi, Ravi Janardan, Michiel Smid, Jörg Schwerdt
In Layered Manufacturing, the choice of the build direction for the model influences several design criteria, including the number of layers, the volume and contact-area of the support structures,...
Gautam Das, Sanjiv Kapoor, Michiel Smid
We consider the problems of computing r-approximate traveling salesman tours and r-approximate minimum spanning trees for a set of n points in IR d , where d 1 is a constant. In the algebraic...
On Some Geometric Optimization Problems in Layered Manufacturing (1997)
Jayanth Majhi, Ravi Janardan, Michiel Smid, Prosenjit Gupta
Efficient geometric algorithms are given for optimization problems arising in layered manufacturing, where a 3D object is built by slicing its CAD model into layers and manufacturing the layers...
A Technique for Adding Range Restrictions to Generalized Searching Problems (1997)
Prosenjit Gupta, Ravi Janardan, Michiel Smid
In a generalized searching problem, a set S of n colored geometric objects has to be stored in a data structure, such that for any given query object q, the distinct colors of the objects of S...
Fast algorithms for collision and proximity problems involving moving geometric objects (1996)
Prosenjit Gupta, Ravi Janardan, Michiel Smid
Consider a set of geometric objects, such as points, line segments, or axesparallel hyperrectangles in IR d, that move with constant but possibly different velocities along linear trajectories....
Prosenjit Gupta Ravi, Ravi Janardan, Michiel Smid
Let S be a set of convex polygons in the plane with a total of n vertices, where a polygon consists of the boundary as well as the interior. Efficient algorithms are presented for the problem of...
Selected Topics in Data Structures (1996)
Michiel Smid, K. Mehlhorn Data Structures, Volume Multi-dimensional Searching, K. Mehlhorn, S. Naher, Dynamic Algorithmica
Introduction through Randomized Algorithms. Prentice Hall, Englewood Cliffs, 1994. [17] M.H. Overmars. The Design of Dynamic Data Structures. Lecture Notes in Computer Science, Vol. 156,...
Lower Bounds for Computing Geometric Spanners and Approximate Shortest Paths (1996)
Danny Chen, Danny Z. Chen, Gautam Das, Michiel Smid
We consider the problems of constructing geometric spanners, possibly containing Steiner points, for sets of points in the d-dimensional space IR d , and constructing spanners and approximate...
On the Circumradius of Acute Point Sets (1996)
A set of points in IR n is said to be in acute position, if the angle determined by any triple of points is at most equal to ß=2. This paper considers the problem of computing the maximum...
Lower Bounds for Computing Geometric Spanners and Approximate Shortest Paths (1996)
Danny Z. Chen, Gautam Das, Michiel Smid
We consider the problems of constructing geometric spanners, possibly containing Steiner points, for sets of points in the d-dimensional space IR d , and constructing spanners and approximate...
Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane (1996)
Srinivasa Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel Smid, Christos D. Zaroliagis
. We consider the problem of finding an obstacle-avoiding path between two points s and t in the plane, amidst a set of disjoint polygonal obstacles with a total of n vertices. The length of this...
Prosenjit Gupta, Ravi Janardan, Michiel Smid
Let S be a set of convex polygons in the plane with a total of n vertices, where a polygon consists of the boundary as well as the interior. Efficient algorithms are presented for the problem of...
A Technique for Adding Range Restrictions to Generalized Searching Problems (1996)
Prosenjit Gupta, Ravi Janardan, Michiel Smid
In a generalized searching problem, a set S of n colored geometric objects has to be stored in a data structure, such that for any given query object q, the distinct colors of the objects of S...
ARTICLE NO. AL960824 More Efficient Parallel Totally Monotone Matrix Searching* (1996)
Phillip G. Bradford, Rudolf Fleischer, Michiel Smid
We give a parallel algorithm for computing all row minima in a totally monotone n � n matrix which is simpler and more work efficient than previous polylog-time algorithms. It runs in OŽ lg n lg...
Prosenjit Gupta, Ravi Janardan, Michiel Smid
Let S be a set of convex polygons in the plane with a total of n vertices, where a polygon consists of the boundary as well as the interior. E�cient algorithms are presented for the problem of...
Algorithms for Some Intersection Searching Problems Involving Curved Objects (1995)
Prosenjit Gupta, Ravi Janardan, Michiel Smid
Two classes of geometric intersection searching problems are considered, i.e., problems in which a set S of geometric objects is to be preprocessed into a data structure so that for any query object...
Euclidean Spanners: Short, Thin, and Lanky (1995)
Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel Smid
Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest...
The Rectangle Enclosure and Point-Dominance Problems Revisited (1995)
Prosenjit Gupta, Ravi Janardan, Michiel Smid, Bhaskar Dasgupta
We consider the problem of reporting the pairwise enclosures in a set of n axes-parallel rectangles in IR 2 , which is equivalent to reporting dominance pairs in a set of n points in IR 4 . Over a...
Efficient Construction of a Bounded Degree Spanner with Low Weight (1995)
Let S be a set of n points in IR d and let t ? 1 be a real number. A t-spanner for S is a graph having the points of S as its vertices such that for any pair p; q of points there is a path between...
Euclidean Spanners: Short, Thin, and Lanky (1995)
Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, Michiel Smid
Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest...
An optimal algorithm for the on-line closest-pair problem (1994)
Christian Schwarz, Michiel Smid, Jack Snoeyink
problem
The Rectangle Enclosure and Point-Dominance Problems Revisited (1994)
Prosenjit Gupta, Ravi Janardan, Michiel Smid, Bhaskar Dasgupta
We consider the problem of reporting the pairwise enclosures among a set of n axes-parallel rectangles in IR 2 , which is equivalent to reporting dominance pairs in a set of n points in IR 4 . For...
Efficient Construction of a Bounded Degree Spanner with Low Weight (1994)
Sunil Arya Michiel, Michiel Smid
Let S be a set of n points in IR d and let t ? 1 be a real number. A t-spanner for S is a graph having the points of S as its vertices such that for any pair p; q of points there is a path between...
New Techniques For Exact And Approximate Dynamic Closest-Point Problems (1994)
. Let S be a set of n points in IR D . It is shown that a range tree can be used to find an L1-nearest neighbor in S of any query point, in O((logn) D\Gamma1 log log n) time. This data structure has...
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions (1994)
Sunil Arya, David M. Mount, Michiel Smid
Let S be a set of n points in IR d and let t ? 1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a...
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions (1994)
Sunil Arya, David M. Mount, Michiel Smid
Let S be a set of n points in IR d and let t ? 1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a...
Dynamic algorithms for geometric spanners of small diameter: Randomized solutions (1994)
Sunil Arya, David M. Mount, Michiel Smid
Let S be a set of n points in IR d and let t ? 1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a...
Randomized data structures for the dynamic closest-pair problem (1993)
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid, Siam J. Comput C
Abstract. We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in...
Randomized Data Structures for the Dynamic Closest-Pair Problem (1993)
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid
We describe a new randomized data structure, the sparse partition, for solving the dynamic closestpair problem. Using this data structure the closest pair of a set of n points in D-dimensional space,...
Computing a Largest Empty Anchored Cylinder, and Related Problems
Frank Follert, Elmar Schömer, Jüörgen Sellen, Michiel Smid, Christian Thiel
Let S be a set of n points in IR d , and let each point p of S have a positive weight w(p). We consider the problem of computing a ray R emanating from the origin (resp. a line l through the origin)...
Computing a Largest Empty Anchored Cylinder, and Related Problems
Frank Follert, Elmar Schömer, Jürgen Sellen, Michiel Smid, Christian Thiel
Let S be a set of n points in IR d , and let each point p of S have a positive weight w(p). We consider the problem of computing a ray R emanating from the origin (resp. a line l through the origin)...