Abstract An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in $$\mathbb {R}^3$$ R 3 consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in $$\mathbb {R}^3$$ R 3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in $$\mathbb {R}^3$$ R 3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in $$\mathbb {R}^3$$ R 3 (with prescribed normal direction of one of the planes) in time $$O (n^{7/3})$$ O ( n 7 / 3 ) . A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).

We study the problem of computing the L₁-distance between two piecewise-linear bivariate functions f and g, defined over a bounded polygonal domain 𝕄 ⊂ ℝ², that is, computing the quantity ‖f-g‖₁ = ∫_𝕄 |f(x,y)-g(x,y)| dx dy. If f and g are defined by linear interpolation over triangulations 𝐓_f and 𝐓_g, respectively, of 𝕄 with a total of n triangles, we show that ‖f-g‖₁ can be computed in Õ(n^α) time, where α = max{(ω+1)/2, 8/5}, ω is the matrix multiplication exponent, and Õ notation hides factors of the form n^ε for any ε > 0. This bound holds for the currently best known value of ω, which is approximately 2.37. More generally, if the complexity of the overlay of 𝐓_f and 𝐓_g is κ, then the runtime of our algorithm is Õ(κ^{α-1}n^{2-α}).

Let $P$ be a polygonal curve with $n$ vertices in the plane. We construct a data structure of size $O(n \log n)$ suited for simplification queries of the following kind. Given a query line $\ell$ and an integer $k\ge1$, find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to $P$, among all such curves. Using our data structure, a query can be handled in $O(k^2 \log^3 n + k\log^4 n)$ time. More generally, a geometric tree $T$ on $n$ vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair $u$, $v$ of its vertices, a line $\ell$, and an integer $k\ge1$, one can find a curve $Q$ on $\ell$ with at most $k$ vertices that minimizes the discrete Fréchet distance to the path from $u$ to $v$ in $T$, in time $O(k^2 \mathop{polylog} n)$. For the general dimension-reduction problem, where $P$ is a curve in $\mathbb{R}^d$ ($d \ge 3$), $0 < \varepsilon_0 < 1$ is a real parameter, and a query specifies a $g$-flat $h$ ($1 \le g \le d-1$) and an integer $k \ge 1$, we construct a data structure of size $O(n\log n + f(\varepsilon_0) n)$, where $f(\varepsilon_0)=(1+1/\varepsilon_0)^{(d-1)/2}$, that allows us to find a curve $Q$ on $h$ with at most $k$ vertices, whose discrete Fréchet distance to $P$ is at most $1+\varepsilon_0$ times the distance of $Q^*$ to $P$, where $Q^*$ is such a curve that minimizes the distance to $P$. The query handling time is $O(f(\varepsilon_0) k^2 \log^2 n)$.

Abstract Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of $$\mathbb {R}^2$$ and let $$\mathcal {D}=\{D_1,\ldots,D_n\}$$ be a set of geodesic disks with respect to the metric d. We prove that $$\mathcal {G}^{\times }(\mathcal {D})$$ , the intersection graph of the disks in $$\mathcal {D}$$ , has a clique-based separator consisting of $$O(n^{3/4+\varepsilon })$$ cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for q-Coloring that runs in time $$2^{O(n^{3/4+\varepsilon })}$$ , assuming the boundaries of the disks $$D_i$$ can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses $$O(n^{7/4+\varepsilon })$$ storage and can report the hop distance between any two nodes in $$\mathcal {G}^{\times }(\mathcal {D})$$ in $$O(n^{3/4+\varepsilon })$$ time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.

Let \(\mathcal{T}\) be a set of \(n\) flat (planar) semi-algebraic regions in \(\mathbb{R}^{3}\) of constant complexity (e.g., triangles, disks), which we call plates . We wish to preprocess \(\mathcal{T}\) into a data structure so that for a query object \(\gamma\) , which is also a plate, we can quickly answer various intersection queries , such as detecting whether \(\gamma\) intersects any plate of \(\mathcal{T}\) , reporting all the plates intersected by \(\gamma\) , or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in \(\mathbb{R}^{3}\) ( arcs , for short), or (ii) the input objects are arcs and the query objects are plates in \(\mathbb{R}^{3}\) . Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if \(\mathcal{T}\) is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses \(O^{*}(n^{4/3})\) storage (where the \(O^{*}(\cdot)\) notation hides factors of the form \(n^{\varepsilon}\) , for an arbitrarily small \(\varepsilon>0\) ) and answers an arc-intersection query in \(O^{*}(n^{2/3})\) time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter \(s\in[n^{4/3},n^{t_{q}}]\) , where \({t_{q}}\geq 3\) is the number of real parameters needed to specify a query arc, the query time can be decreased to \(O^{*}((n/s^{1/{t_{q}}})^{\tfrac{2/3}{1-1/{t_{q}}}})\) by increasing the storage to \(O^{*}(s)\) . Our approach can be extended to many additional intersection-searching problems in three dimensions, even when the input or query objects are not flat.

Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, giving rise to the assembly partitioning sub-problem: Given a set \(A\) of parts, find a subset \(S\subset A\) , referred to as a subassembly, such that \(S\) can be rigidly translated to infinity along a prescribed direction without colliding with \(A\setminus S\) . While assembly partitioning is efficiently solvable, it is further desirable for the parts of a subassembly to be easily held together. This motivates the problem that we study, called connected-assembly-partitioning , which additionally requires each of the two subassemblies, \(S\) and \(A\setminus S\) , to be connected. We obtain the following results. — We show that this problem is NP-complete, settling an open question posed by Wilson et al. 30 years ago, even when \(A\) consists of unit-grid squares (i.e., \(A\) is polyomino-shaped). For assemblies composed of polygons, we also show that deciding whether complete (dis)assembly is possible by repeatedly applying connected-assembly-partitioning, is NP-complete. Toward these results, we prove the NP-hardness of a new Planar 3-SAT variant having an adjacency requirement for variables appearing in the same clause, which may be of independent interest. — On the positive side, we give an \(O(2^{k}n^{2})\) -time fixed-parameter tractable algorithm (requiring low degree polynomial-time preprocessing) for an assembly \(A\) consisting of polygons in the plane, where \(n=|A|\) and \(k=|S|\) . We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in \(O(n)\) -time.

An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).

Let $d$ be a (well-behaved) shortest-path metric defined on a path-connected subset of $\mathbb{R}^2$ and let $\mathcal{D}=\{D_1,\ldots,D_n\}$ be a set of geodesic disks with respect to the metric $d$. We prove that $\mathcal{G}^{\times}(\mathcal{D})$, the intersection graph of the disks in $\mathcal{D}$, has a clique-based separator consisting of $O(n^{3/4+\varepsilon})$ cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for $q$-COLORING that runs in time $2^{O(n^{3/4+\varepsilon})}$, assuming the boundaries of the disks $D_i$ can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses $O(n^{7/4+\varepsilon})$ storage and can report the hop distance between any two nodes in $\mathcal{G}^{\times}(\mathcal{D})$ in $O(n^{3/4+\varepsilon})$ time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes.

It is unlikely that the discrete Fréchet distance between two curves of length $n$ can be computed in strictly subquadratic time. We thus consider the setting where one of the curves, $P$, is known in advance. In particular, we wish to construct data structures (distance oracles) of near-linear size that support efficient distance queries with respect to $P$ in sublinear time. Since there is evidence that this is impossible for query curves of length $Θ(n^α)$, for any $α> 0$, we focus on query curves of (small) constant length, for which we are able to devise distance oracles with the desired bounds. We extend our tools to handle subcurves of the given curve, and even arbitrary vertex-to-vertex subcurves of a given geometric tree. That is, we construct an oracle that can quickly compute the distance between a short polygonal path (the query) and a path in the preprocessed tree between two query-specified vertices. Moreover, we define a new family of geometric graphs, $t$-local graphs (which strictly contains the family of geometric spanners with constant stretch), for which a similar oracle exists: we can preprocess a graph $G$ in the family, so that, given a query segment and a pair $u,v$ of vertices in $G$, one can quickly compute the smallest discrete Fréchet distance between the segment and any $(u,v)$-path in $G$. The answer is exact, if $t=1$, and approximate if $t>1$.

We present subquadratic algorithms in the algebraic decision-tree model for several 3Sum-hard geometric problems, all of which can be reduced to the following question: Given two sets A, B, each consisting of n pairwise disjoint segments in the plane, and a set C of n triangles in the plane, we want to count, for each triangle Δ∈C, the number of intersection points between the segments of A and those of B that lie in Δ. We present solutions in the algebraic decision-tree model whose cost is O(n60/31+ε), for any ε>0. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal et al. (2021) [3]. A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the order type of the lines, a “handicap” that turns out to be beneficial for speeding up our algorithm.

Let $\mathcal{T}$ be a set of $n$ flat (planar) semi-algebraic regions in $\mathbb{R}^3$ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess $\mathcal{T}$ into a data structure so that for a query object $γ$, which is also a plate, we can quickly answer various intersection queries, such as detecting whether $γ$ intersects any plate of $\mathcal{T}$, reporting all the plates intersected by $γ$, or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree parametrized algebraic arcs in $\mathbb{R}^3$ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in $\mathbb{R}^3$. Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we present many different data structures for intersection queries, which also provide trade-offs between their size and query time. For example, if $\mathcal{T}$ is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses $O^*(n^{4/3})$ storage (where the $O^*(\cdot)$ notation hides factors of the form $n^ε$, for an arbitrarily small $ε>0$) and answers an arc-intersection query in $O^*(n^{2/3})$ time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter $s\in [n^{4/3}, n^{t_q}]$, where ${t_q}\ge 3$ is the number of real parameters needed to specify a query arc, the query time can be decreased to $O^*((n/s^{1/{t_q}})^{\tfrac{2/3}{1-1/{t_q}}})$ by increasing the storage to $O^*(s)$.

We prove that some exact geometric pattern matching problems reduce in linear time to k -SUM when the pattern has a fixed size k. This holds in the real RAM model for searching for a similar copy of a set of $$k\ge 3$$ points within a set of n points in the plane, and for searching for an affine image of a set of $$k\ge d+2$$ points within a set of n points in d-space. As corollaries, we obtain improved real RAM algorithms and decision trees for the two problems. In particular, they can be solved by algebraic decision trees of near-linear height.

We present subquadratic algorithms in the algebraic decision-tree model for several \textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segments in the plane, and a set $C$ of $n$ triangles in the plane, we want to count, for each triangle $Δ\in C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $Δ$. The problems considered in this paper have been studied by Chan~(2020), who gave algorithms that solve them, in the standard real-RAM model, in $O((n^2/\log^2n)\log^{O(1)}\log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+\varepsilon})$, for any $\varepsilon>0$. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl~(2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the \emph{order type} of the lines, a "handicap" that turns out to be beneficial for speeding up our algorithm.

Assembly planning is a fundamental problem in robotics and automation, which aims to design a sequence of motions that brings the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, assembly partitioning, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected. In this paper we study a natural special case of the connected-assembly-partitioning problem: Given a connected set A of unit-grid squares in the plane, find a connected subset S ⊂ A such that A \ S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A\S. We show that even this simple problem is NP-complete, settling an open question posed by Wilson et al. a quarter of a century ago [16]. We complement the hardness result with two positive results. First, we show that the problem is fixed-parameter tractable and present an O(2kn2)-time algorithm, where n = |A| and k = |S|. Second, we describe a special case of this problem where a connected partition can always be found in O(n) time.

In 2015, Guth proved that if $\EuScript{S}$ is a collection of $n$ $g$-dimensional semialgebraic sets in ${\mathbb{R}}^d$ and if $D\geq 1$ is an integer, then there is a $d$-variate polynomial $P$ of degree at most $D$ so that each connected component of $\mathbb{R}^d\setminus Z(P)$ intersects $O(n/D^{d-g})$ sets from $\EuScript{S}$. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently---the expected running time of our algorithm is linear in $\lvert \EuScript{S}\rvert$. Our approach exploits the technique of quantifier elimination combined with that of $\eps$-samples. We also present an extension of our construction to multilevel polynomial partitioning for semialgebraic sets in $\mathbb{R}^d$. We present five applications of our result. The first is a data structure for answering point-enclosure queries among a family of semialgebraic sets in $\mathbb{R}^d$ in $O(\log n)$ time, with storage complexity and expected preprocessing time of $O(n^{d+\eps})$. The second is a data structure for answering range-searching queries with semialgebraic ranges in $\mathbb{R}^d$ in $O(\log n)$ time, with $O(n^{t+\eps})$ storage and expected preprocessing time, where $t > 0$ is an integer that depends on $d$ and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semialgebraic sets in $\mathbb{R}^{d}$ in $O(\log^2 n)$ time, with $O(n^{d+\eps})$ storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in $\mathbb{R}^2$ into pseudosegments. The fifth application is for eliminating depth cycles among triangles in $\mathbb{R}^3$, where we show a nearly optimal algorithm to cut $n$ pairwise disjoint nonvertical triangles in ${\mathbb{R}}^3$ into pieces that form a depth order.

Let V be a set of n points in mathcal R d , called voters . A point p ∈ mathcal R d is a plurality point for V when the following holds: For every q ∈ mathcal R d , the number of voters closer to p than to q is at least the number of voters closer to q than to p . Thus, in a vote where each v ∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q . For most voter sets, a plurality point does not exist. We therefore introduce the concept of β-plurality points , which are defined similarly to regular plurality points, except that the distance of each voter to p (but not to q ) is scaled by a factor β , for some constant 0< β ⩽ 1. We investigate the existence and computation of β -plurality points and obtain the following results. • Define β * d := {β : any finite multiset V in mathcal R d admits a β-plurality point. We prove that β * d = √3/2, and that 1/√ d ⩽ β * d ⩽ √ 3/2 for all d ⩾ 3. • Define β ( p, V ) := sup {β : p is a β -plurality point for V }. Given a voter set V in mathcal R 2 , we provide an algorithm that runs in O ( n log n ) time and computes a point p such that β ( p , V ) ⩾ β * b . Moreover, for d ⩾ 2, we can compute a point p with β ( p , V ) ⩾ 1/√ d in O ( n ) time. • Define β ( V ) := sup { β : V admits a β -plurality point}. We present an algorithm that, given a voter set V in mathcal R d , computes an ((1-ɛ)ċ β ( V ))-plurality point in time O n 2 ɛ 3d-2 ċ log n ɛ d-1 ċ log 2 1ɛ).

Let V be a set of n points in ℝ^d, called voters. A point p ∈ ℝ^d is a plurality point for V when the following holds: for every q ∈ ℝ^d the number of voters closer to p than to q is at least the number of voters closer to q than to p. Thus, in a vote where each v ∈ V votes for the nearest proposal (and voters for which the proposals are at equal distance abstain), proposal p will not lose against any alternative proposal q. For most voter sets a plurality point does not exist. We therefore introduce the concept of β-plurality points, which are defined similarly to regular plurality points except that the distance of each voter to p (but not to q) is scaled by a factor β, for some constant 0<β⩽1. We investigate the existence and computation of β-plurality points, and obtain the following results. - Define β^*_d := sup{β : any finite multiset V in ℝ^d admits a β-plurality point}. We prove that β^*₂ = √3/2, and that 1/√d ⩽ β^*_d ⩽ √3/2 for all d⩾3. - Define β(V) := sup {β : V admits a β-plurality point}. We present an algorithm that, given a voter set V in {ℝ}^d, computes an (1-ε)⋅ β(V) plurality point in time O(n²/ε^(3d-2) ⋅ log(n/ε^(d-1)) ⋅ log²(1/ε)).

We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets A, B, and C of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in A×B×C, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly O(n^(28/15)) constant-degree polynomial sign tests, for the special case where two of the sets lie on one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to any other problem where we seek a triple that satisfies a single polynomial equation, e.g., determining whether A× B× C contains a triple spanning a unit-area triangle. This result extends recent work by Barba et al. [Luis Barba et al., 2019] and by Chan [Timothy M. Chan, 2020], where all three sets A, B, and C are assumed to be one-dimensional. While there are common features in the high-level approaches, here and in [Luis Barba et al., 2019], the actual analysis in this work becomes more involved and requires new methods and techniques, involving polynomial partitions and other related tools. As a second application of our technique, we again have three n-point sets A, B, and C in the plane, and we want to determine whether there exists a triple (a,b,c) ∈ A×B×C that simultaneously satisfies two real polynomial equations. For example, this is the setup when testing for the existence of pairs of similar triangles spanned by the input points, in various contexts discussed later in the paper. We show that problems of this kind can be solved with roughly O(n^(24/13)) constant-degree polynomial sign tests. These problems can be extended to higher dimensions in various ways, and we present subquadratic solutions to some of these extensions, in the algebraic decision-tree model.

Dynamic Time Warping (DTW) is a well-known similarity measure for curves, i.e., sequences of points, and especially for time series. We study several proximity problems for curves, where dynamic time warping is the underlying similarity measure. More precisely, we focus on the variants of these problems, in which, whenever we refer to the dynamic time warping distance between two curves, one of them is a line segment (i.e., a sequence of length two). These variants already reveal some of the difficulties that occur when dealing with the more general ones. Specifically, we study the following three problems: (i) distance oracle: given a curve C in ℝ^d, preprocess it to accommodate distance computations between query segments and C, (ii) segment center: given a set 𝒞 of curves in ℝ^d, find a segment s that minimizes the maximum distance between s and a curve in 𝒞, and (iii) segment nearest neighbor: given 𝒞, construct a data structure for segment nearest neighbor queries, i.e., return the curve in 𝒞 which is closest to a query segment s. We present solutions to these problems in any constant dimension d ≥ 1, using L_∞ for inter-point distances. We also consider the approximation version of the first problem, using L₁ for inter-point distances. That is, given a length-m curve C in ℝ^d, we construct a data structure of size O(m log m) that allows one to compute a 2-approximation of the distance between a query segment s and C in O(log³ m) time. Finally, we describe an interesting experimental study that we performed, which is related to the first problem above.

Abstract It is well known that any set of n intervals in $$\mathbb {R} ^1$$ R1 admits a non-monochromatic coloring with two colors and a conflict-free coloring with three colors. We investigate generalizations of this result to colorings of objects in more complex 1-dimensional spaces, namely so-called tree spaces and planar network spaces.

We consider a set of transmitters broadcasting simultaneously on the same frequency under the signal to interference plus noise ratio (SINR) model. Transmission power may vary from one transmitter to another, and a transmitter's signal strength at a given point is modeled by the transmitter's power divided by some constant power $\alpha$ of the distance it traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger by a specified ratio than the signals of all other transmitters combined. An SINR query is to determine whether a receiver at a given location can hear any transmitter, and if yes, which one. An approximate answer to an SINR query is such that one gets a definite yes or definite no, when the ratio between the strongest signal and all other signals combined is well above or well below the reception threshold, while the answer in the intermediate range is allowed to be either yes or no. We describe compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where transmitters may be inserted and deleted over time. We distinguish between two main variants---uniform power and nonuniform power. In both variants the preprocessing time is $O(n\,{polylog} n)$ and the amortized update time is $O({\rm polylog} n)$, while the query time is $O({polylog} n)$ for uniform power, and randomized time $O(\sqrt{n}\,{polylog} n)$ with high probability for nonuniform power. Finally, we observe that in the static context the latter data structure can be implemented differently, so that the query time is also $O({polylog} n)$, thus significantly improving all previous results for this problem.

In 2015, Guth [ Math. Proc. Cambridge Philos. Soc., 159 (2015), pp. 459--469] proved that for any set of $k$-dimensional bounded complexity varieties in ${\mathbb R}^d$ and for any positive integer $D$, there exists a polynomial of degree at most $D$ whose zero set divides ${\mathbb R}^d$ into open connected sets so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz [ Ann. Math., 181 (2015), pp. 155--190] for points. Guth's proof relies on a variant of the Borsuk--Ulam theorem, and for $k>0$, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in ${{\mathbb R}}^3$. We present an efficient algorithmic construction for this setting. Given a set of $n$ input algebraic curves and a positive integer $D$, we efficiently construct a decomposition of space into $O(D^3\log^3{D})$ open “cells,” each of which meets $O(n/D^2)$ curves from the input. The construction time is $O(n^2)$. For the case of lines in 3-space, we present an improved implementation whose running time is $O(n^{4/3} { polylog }{n})$. The constant of proportionality in both time bounds depends on $D$ and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among nonvertical lines in 3-space, recently studied by Aronov and Sharir [ Discrete Comput. Geom., 59 (2018), pp. 725--741] and show an algorithm that cuts $n$ such lines into $O(n^{3/2+\varepsilon})$ pieces that are depth-cycle free for any $\varepsilon > 0$. The algorithm runs in $O(n^{3/2+\varepsilon})$ time, which is a considerable improvement over the previously known algorithms.

In 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in R^d and if D >= 1 is an integer, then there is a d-variate polynomial P of degree at most D so that each connected component of R^d \ Z(P) intersects O(n/D^{d-g}) sets from S. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently - the expected running time of our algorithm is linear in |S|. Our approach exploits the technique of quantifier elimination combined with that of epsilon-samples. We present four applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in R^d in O(log n) time, with storage complexity and expected preprocessing time of O(n^{d+epsilon}). The second is a data structure for answering range search queries with semi-algebraic ranges in O(log n) time, with O(n^{t+epsilon}) storage and expected preprocessing time, where t > 0 is an integer that depends on d and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semi-algebraic sets in R^{d} in O(log^2 n) time, with O(n^{d+epsilon}) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic planar curves into pseudo-segments.

In 2015, Guth proved that, for any set of k-dimensional varieties in ℝ3 and for any positive integer D, there exists a polynomial of degree at most D whose zero-set divides ℝ3 into open connected “cells,” so that only a small fraction of the given varieties intersect each cell. Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for k > 0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for curves (or even lines) in ℝ3. We present an efficient algorithmic construction for this setting. Given a set of n input curves and a positive integer D, we efficiently construct a decomposition of space into O(D3 log3 D) open cells, each of which meets at most O(n/D2) curves from the input. The construction time is O(n2), where the constant of proportionality depends on D and the maximum degree of the polynomials defining the input curves. For the case of lines in 3-space we present an improved implementation, whose running time is O(n4/3 polylog n). As an application, we revisit the problem of eliminating depth cycles among non-vertical pairwise disjoint triangles in 3-space, recently studied by Aronov et al. (2017) and De Berg (2017). Our main result is an algorithm that cuts n triangles into O(n3/2+ε) pieces that are depth cycle free, for any ε > 0. The algorithm runs in O(n3/2+ε) time, which is nearly worst-case optimal. We also sketch several other applications of our effective partitioning for curves in ℝ3.

Let A and B be two sets of points in R^d, where |A|=|B|=n and the distance between them is defined by some bipartite measure dist(A, B). We study several problems in which the goal is to translate the set B, so that dist(A, B) is minimized. The main measures that we consider are (i) the diameter in two and three dimensions, that is diam(A,B) = max {d(a,b) | a in A, b in B}, where d(a,b) is the Euclidean distance between a and b, (ii) the uniformity in the plane, that is uni(A,B) = diam(A,B) - d(A,B), where d(A,B)=min{d(a,b) | a in A, b in B}, and (iii) the union width in two and three dimensions, that is union_width(A,B) = width(A cup B). For each of these measures we present efficient algorithms for finding a translation of B that minimizes the distance: For diameter we present near-linear-time algorithms in R^2 and R^3, for uniformity we describe a roughly O(n^{9/4})-time algorithm, and for union width we offer a near-linear-time algorithm in R^2 and a quadratic-time one in R^3.

With the ubiquitous adoption of smartphones and mobile devices, it is now common practice for one's location to be sensed, collected and likely shared through social platforms. While such data can be helpful for many applications, users start to be aware of the privacy issue in handling location and trajectory data. While some users may voluntarily share their location information (e.g., for receiving location-based services, or for crowdsourcing systems), their location information may lead to information leaks about the whereabouts of other users, through the co-location of events when two users are at the same location at the same time and other side information, such as upper bounds of movement speed. It is therefore crucial to understand how much information one can derive about other's positions through the co-location of events and occasional GPS location leaks of some of the users. In this paper we formulate the problem of inferring locations of mobile agents, present theoretically-proven bounds on the amount of information that could be leaked in this manner, study their geometric nature, and present algorithms matching these bounds. We will show that even if a very weak set of assumptions is made on trajectories' patterns, and users are not obliged to follow any 'reasonable' patterns, one could infer very accurate estimation of users' locations even if they opt not to share them. Furthermore, this information could be obtained using almost linear-time algorithms, suggesting the practicality of the method even for huge volumes of data.

Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any ∊ > 0, the triangles can be cut into O(n3/2+∊) pieces, where each piece is a connected semi-algebraic set whose description complexity depends only on the choice of ∊, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces. This work extends the recent study by two of the authors on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth, which leads to a recursive procedure for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear. Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

We show that the union of n translates of a convex body in $$\mathbb {R}^3$$ can have $$\varTheta (n^3)$$ holes in the worst case, where a hole in a set X is a connected component of $$\mathbb {R}^3 \setminus X$$ . This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions.

Given n non-vertical lines in 3-space, their vertical depth (above/below) relation can contain cycles. We show that the lines can be cut into O(n3/2polylog n) pieces, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. As a consequence, we deduce that the number of pairwise non-overlapping cycles, namely, cycles whose xy-projections do not overlap, is O(n3/2polylog n); this bound too is almost tight in the worst case.

Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has a wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest-neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability and (ii) estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.

In the trajectory segmentation problem, we are given a polygonal trajectory with n vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to be solvable efficiently for monotone criteria: criteria with the property that if they hold on a certain segment, they also hold on every subsegment of that segment. To the best of our knowledge, no theoretical results are known for nonmonotone criteria. We present a broader study of the segmentation problem, and suggest a general framework for solving it, based on the start-stop diagram : a 2-dimensional diagram that represents all valid and invalid segments of a given trajectory. This yields two subproblems: (1) computing the start-stop diagram, and (2) finding the optimal segmentation for a given diagram. We show that (2) is NP-hard in general. However, we identify properties of the start-stop diagram that make the problem tractable and give a polynomial-time algorithm for this case. We study two concrete nonmonotone criteria that arise in practical applications in more detail. Both are based on a given univariate attribute function f over the domain of the trajectory. We say a segment satisfies an outlier-tolerant criterion if the value of f lies within a certain range for at least a given percentage of the length of the segment. We say a segment satisfies a standard deviation criterion if the standard deviation of f over the length of the segment lies below a given threshold. We show that both criteria satisfy the properties that make the segmentation problem tractable. In particular, we compute an optimal segmentation of a trajectory based on the outlier-tolerant criterion in O ( n 2 log n + kn 2 ) time and on the standard deviation criterion in O ( kn 2 ) time, where n is the number of vertices of the input trajectory and k is the number of segments in an optimal solution.

We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M , induced by the L 2 norm—that is, ‖ f - g ‖2 = √∫ M ( f - g ) 2 . If f is defined by linear interpolation over a triangulation of M with n triangles and g is defined over another such triangulation, the obvious naive algorithm requires Θ( n 2 ) arithmetic operations to compute this distance. We show that it is possible to compute it in O ( n log 4 n log log n ) arithmetic operations by reducing the problem to multipoint evaluation of a certain type of polynomials. We also present several generalizations and an application to terrain matching.

The SINR model for the quality of wireless connections has been the subject of extensive recent study. It attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of n simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the SINR diagram, which partitions the space into n regions where each of the transmitters can be heard and the remaining space where no transmitter can be heard. Efficient point location in the SINR diagram, i.e., being able to build a data structure that facilitates determining, for a query point, whether any transmitter is heard there, and if so, which one, has been recently investigated in several papers. These planar data structures are constructed in time at least quadratic in n and support logarithmic-time approximate queries. Moreover, the performance of some of the proposed structures depends strongly not only on the number n of transmitters and on the approximation parameter $$\varepsilon $$ , but also on some geometric parameters that cannot be bounded a priori as a function of n or $$\varepsilon $$ . In this paper, we address the question of batched point location queries, i.e., answering many queries simultaneously. Specifically, in one dimension, we can answer n queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately. All these results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time in these results depends only on n and $$\varepsilon $$ . Finally, these results demonstrate the (so far underutilized) power of combining algebraic tools with those of computational geometry and other fields.

We show that, for any $\gamma > 0$, the combinatorial complexity of the union of $n$ locally $\gamma$-fat objects of constant complexity in the plane is $\frac{n}{\gamma^4} 2^{O(\log^*n)}$. For the special case of $\gamma$-fat triangles, the bound improves to $O(n \log^*{n} + \frac{n}{\gamma}\log^2{\frac{1}{\gamma}})$.

Nearest-neighbor (NN) search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability; (ii) estimating, within a specified additive error, the probability of a point being the nearest neighbor of a query point; (iii) using it to return the point that maximizes the probability being the nearest neighbor, or all the points with probabilities greater than some threshold to be the NN. We also present some experimental results to demonstrate the effectiveness of our approach.

In the trajectory segmentation problem we are given a polygonal trajectory with n vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to be solvable efficiently for monotone criteria: criteria with the property that if they hold on a certain segment, they also hold on every subsegment of that segment [4]. To the best of our knowledge, no theoretical results are known for non-monotone criteria. We present a broader study of the segmentation problem, and suggest a general framework for solving it, based on the start-stop diagram: a 2-dimensional diagram that represents all valid and invalid segments of a given trajectory. This yields two subproblems: (i) computing the start-stop diagram, and (ii) finding the optimal segmentation for a given diagram. We show that (ii) is NP-hard in general. However, we identify properties of the start-stop diagram that make the problem tractable, and give polynomial-time algorithm for this case. We study two concrete non-monotone criteria that arise in practical applications in more detail. Both are based on a given univariate attribute function f over the domain of the trajectory. We say a segment satisfies an outlier-tolerant criterion if the value of f lies within a certain range for at least a given percentage of the length of the segment. We say a segment satisfies a standard deviation criterion if the standard deviation of f over the length of the segment lies below a given threshold. We show that both criteria satisfy the properties that make the segmentation problem tractable. In particular, we compute an optimal segmentation of a trajectory based on the outlier-tolerant criterion in O(n2 log n+kn2) time, and on the standard deviation criterion in O(kn2) time, where n is the number of vertices of the input trajectory and k is the number of segments in an optimal solution.

We study the problem of computing correlation between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in three dimensions---polyhedral terrains---can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in $O(n^{4/3}\operatorname{polylog}n)$ expected time, where $n$ is the total number of vertices in the graphs of the two functions. We also present approximation algorithms for minimizing the mean distance between the graphs of univariate and bivariate functions. For univariate functions we present a $(1+\varepsilon)$-approximation algorithm that runs in $O(n (1 + \log^2 (1/\varepsilon)))$ expected time for any fixed $\varepsilon >0$. The $(1+\varepsilon)$-approximation algorithm for bivariate functions runs in $O(n/\varepsilon)$ time, for any fixed $\varepsilon >0$, provided the two functions are defined over the same triangulation of their domain.

We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M. We focus on the distance induced by the L2-norm, that is . If f is defined by linear interpolation over a triangulation of M with n triangles, while g is defined over another such triangulation, the obvious naïve algorithm requires Θ(n2) arithmetic operations to compute this distance. We show that it is possible to compute it in O(n log n) arithmetic operations, by reducing the problem to multi-point evaluation of a certain type of polynomials. We also present an application to terrain matching.

The skeleton of a polyhedral set is the union of its edges and vertices. Let $\mathcal {P}$ be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f max be the maximum complexity of any face of a polytope in $\mathcal {P}$ . We prove that the total length of the skeleton of the union of the polytopes in $\mathcal {P}$ is at most O(α(n)⋅log∗ n⋅logf max) times the sum of the skeleton lengths of the individual polytopes.

Let P be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment inside P. We present a 3-approximation algorithm for the problem of finding a partition with minimum stabbing number. It is based on an algorithm that finds an optimal partition for histograms. We also study Steiner triangulations of a simple (non-rectilinear) polygon P. Here the stabbing number is defined as the maximum number of triangles that can be stabbed by any line segment inside P. We give an O(1)-approximation algorithm for the problem of computing a Steiner triangulation with minimum stabbing number.

We show that, for any fixed δ > 0, the combinatorial complexity of the union of n triangles in the plane, each of whose angles is at least δ, is O(n2α(n) log* n), with the constant of proportionality depending on δ. This considerably improves the twenty-year-old bound O(n log log n), due to Matousek et al. [24, 25].

We study variants of the potato peeling problem on meshed (triangulated) polygons. Given a polygon with holes, and a triangular mesh that covers its interior (possibly using additional vertices), we want to find a largest-area connected set of triangles of the mesh that is convex, or has some other shape-related property. In particular, we consider (i) convexity, (ii) monotonicity, (iii) bounded backturn, and (iv) bounded total turning angle. The first three problems are solved in polynomial time, whereas the fourth problem is shown to be NP-hard.

We study the problem of computing the similarity between two piecewise-linear bivariate functions defined over a common domain, where the surfaces they define in 3D - polyhedral terrains - can be transformed vertically by a linear transformation of the third coordinate (scaling and translation). We present a randomized algorithm that minimizes the maximum vertical distance between the graphs of the two functions, over all linear transformations of one of the terrains, in O(n4/3 polylog n) expected time, where n is the total number of vertices in the graphs of the two functions. We also study the computation of similarity between two univariate or bivariate functions by minimizing the area or volume between their graphs. For univariate functions we give a (1+ε)-approximation algorithm for minimizing the area that runs in O(n/√ε) time, for any fixed ε > 0. The (1 + ε)- approximation algorithm for the bivariate version, where volume is minimized, runs in O(n/ε2) time, for any fixed ε > 0, provided the two functions are defined over the same triangulation of their domain.

We show the existence of $\varepsilon$-nets of size $O\left(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon}\right)$ for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane and “fat” triangular ranges and for point sets in $\boldsymbol{R}^3$ and axis-parallel boxes; these are the first known nontrivial bounds for these range spaces. Our technique also yields improved bounds on the size of $\varepsilon$-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of $\varepsilon$-nets of size $O\left(\frac{1}{\varepsilon}\log\log\log\frac{1}{\varepsilon}\right)$ for the dual range space of “fat” regions and planar point sets (where the regions are the ground objects and the ranges are subsets stabbed by points). Plugging our bounds into the technique of Brönnimann and Goodrich or of Even, Rawitz, and Shahar, we obtain improved approximation factors (computable in expected polynomial time by a randomized algorithm) for the hitting set or the set cover problems associated with the corresponding range spaces.

We present a simple scheme extending the shallow partitioning data structures of Matoušek, which supports efficient approximate halfspace range-counting queries in $\mathbb{R}^d$ with relative error $\varepsilon$. Specifically, the problem is, given a set P of n points in $\mathbb{R}^d$, to preprocess them into a data structure that returns, for a query halfspace h, a number t so that $(1-\varepsilon)|h\cap P|\leq t\leq(1+\varepsilon)|h\cap P|$. One of our data structures requires linear storage and $O(n^{1+\delta})$ preprocessing time, for any $\delta>0$, and answers a query in time $O(\varepsilon^{-\gamma}n^{1-1/\lfloor d/2\rfloor}2^{b\log^\ast n})$ for any $\gamma>2/\lfloor d/2\rfloor$; the choice of $\gamma$ and $\delta$ affects b and the implied constants. Several variants and extensions are also discussed. As presented, the construction of the structure is mostly deterministic, except for one critical randomized step, and so are the query, storage, and preprocessing costs. The quality of approximation, for every query, is guaranteed with high probability. The construction can also be fully derandomized, at the expense of increasing preprocessing time.

We show the existence of ε-nets of size O(1/ε log log 1/ε) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in reals3 and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size

Road network data is often incomplete, making it hard to perform network analysis. This paper discusses the problem of extending partial road networks with reasonable links, using the concept of dilation (also known as crow flight conversion coefficient). To this end, we study how to connect a point (relevant location) inside a polygon (face of the known part of the road network) to the boundary so that the dilation from that point to any point on the boundary is not too large. We provide algorithms and heuristics, and give a computational and experimental analysis.

We study the question of finding a deepest point in an arrangement of regions and provide a fast algorithm for this problem using random sampling, showing it sufficient to solve this problem when the deepest point is shallow. This implies, among other results, a fast algorithm for approximately solving linear programming problems with violations. We also use this technique to approximate the disk covering the largest number of red points, while avoiding all the blue points, given two such sets in the plane. Using similar techniques implies that approximate range counting queries have roughly the same time and space complexity as emptiness range queries.

The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most notably to approximate range counting. We give a simple constructive proof of their existence in general range spaces with finite VC dimension, and of a sharp bound on their size, close to the best known one. We then give a construction of smaller-size relative ε-approximations for range spaces that involve points and halfspaces in two and higher dimensions. The planar construction is based on a new structure--spanning trees with small relative crossing number, which we believe to be of independent interest. In the second part, we consider the approximate halfspace range-counting problem in Rd with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matoušek, yields efficient solutions to this problem. For example, one of our data structures requires linear storage and O(n1+δ) preprocessing time, for any δ>0, and answers a query in time O(ε-γn1-1/⌊ d/2 ⌋ 2b log* n), for any γ > 2/⌊ d/2⌋ the choice of γ and δ affects b and the implied constants. Several variants and extensions are also discussed.

We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R3. The data structure uses O(n2+ε) storage and preprocessing time, and queries can be answered in O(log2 n) time. A trade-off between storage and query time is also possible: for any m with n < m < n2, we can construct a structure that uses O(m1+ε) storage and preprocessing time such that queries take O((n/√m)log2 n) time.We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in R3. For any m with n < m < n3, we can construct a structure that uses O(m1+ε) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m1/3)log n+k) time, where k is the number of answers.

We consider the problem of balancing the load among several service-providing facilities, while keeping the total cost low. Let D be the underlying demand region, and let p1, …, pm be m points representing m facilities. We consider the following problem: Subdivide D into m equal-area regions R1, …, Rm, so that region Ri is served by facility pi, and the average distance between a point q in D and the facility that serves q is minimal.We present constant-factor approximation algorithms for this problem, with the additional requirement that the resulting regions must be convex. As an intermediate result we show how to partition a convex polygon into m=2k equal-area convex subregions so that the fatness of the resulting regions is within a constant factor of the fatness of the original polygon. We also prove that our partition is, up to a constant factor, the best one can get if one's goal is to maximize the fatness of the least fat subregion.We also discuss the structure of the optimal partition for the aforementioned load balancing problem: indeed, we argue that it is always induced by an additive-weighted Voronoi diagram for an appropriate choice of weights.

A closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding whether two sets of n points in ℝ 3 can be separated by a prism, near-quadratic algorithms for separating by a slab or a wedge, and a near-cubic algorithm for separating by a double wedge. The latter three algorithms improve the previous best known results by an order of magnitude, while the prism separability algorithm constitutes an improvement of two orders of magnitude.

Let B be a set of n unit balls in ℝ3. We show that the combinatorial complexity of the space of lines in ℝ3 that avoid all the balls of B is O(n 3+e), for any ε0. This result has connections toproblems in visibility, ray shooting, motion planning andgeometric optimization.

A compact body c in ℝd is κ-round if for every point p∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ>0, the combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n3+ε)) for any ε>0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.

Many algorithmic problems are interesting to both theoreticians and practitioners, but in a different manner. While the theoreticians have traditionally focused on worst-case scenarios which is often not very useful in practice, the practitioners are sometimes stuck in the hacking culture and arrive at solutions that only work well in a few specific cases. An example of such an algorithmic problem is ray shooting.Imposing some data structure to support ray-shooting queries usually helps to improve the efficiency of the algorithm. We focus on one such data structure---the octree. It is flexible and adaptive and has many applications. However, its degree of adaptiveness usually depends on manually selected parameters controlling its termination criteria. It is difficult to fix a set of parameter values that is good for all possible scenes. One approach to resolve this problem is to construct a data structure which tunes itself to the input without using arbitrary preset parameters, so that a single algorithm is suitable for all situations. Surprisingly, only a few investigations have focused on this approach compared to the huge amount of research papers on ray shooting from both the theoreticians and the practitioners. We take some steps in this direction by evaluating several octree construction schemes for use in ray shooting, some widely used in the computer graphics literature (such as bounding the number of objects in a leaf and the maximum depth) and some developed in companion papers as part of this research (cost-driven k-greedy termination criteria). Our experimental results show that the octrees constructed using our schemes are better than those built with a priori fixed parameters.Our octree construction algorithm is driven by a simple cost predictor and has been proven elsewhere to approximate the optimal tree to within a constant factor. We fine-tune the predictor and observe the behavior of our algorithm on octrees built to support a simple ray tracing engine and compare its performance with those of commonly used alternatives. It appears to work well in practice.

We show that a collection of lines in 3-space can be cut into a subquadratic number of pieces, such that all depth cycles defined by triples of lines are eliminated. This partially resolves a long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n77/141-ε)=Ω(n0.546), for any ε>0. Moreover, there always exists a point p ∈ P from which there are at least these many distinct distances to the remaining elements of P. The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.

The ray shooting problem arises in many different contexts. For example, solving it efficiently would ...

(MATH) We show that the number of incidences between m distinct points and n distinct circles in $\reals^3$ is O(m 4/7 n 17/21+m 2/3 n 2/3+m+n); the bound is optimal for m n 3/2. This result extends recent work on point-circle incidences in the plane, but its proof requires a different analysis. The bound improves upon a previous bound, noted by Akutsu et al. [2] and by Agarwal and Sharir [1], but it is not as sharp (when m is small) as the recent planar bound of Aronov and Sharir [3]. Our analysis extends to yield the same bound (a) on the number of incidences between m points and n circles in any dimension d≥ 3, and (b) on the number of incidences between m points and n arbitrary convex plane curves in $\reals^d$, for any d≥ 3, provided that no two curves are coplanar. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space, and were already used to obtain a lower bound for the number of distinct distances in a set of n points in 3-space.

We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for general circles, they nearly coincide with the best known bounds for the number of incidences between m points and n circles.

Article A Helly-type theorem for hyperplane transversals to well-separated convex sets Share on Authors: Boris Aronov Polytechnic University, Brooklyn, NY Polytechnic University, Brooklyn, NYView Profile , Jacob E. Goodman City College, City University of New York, New York, NY City College, City University of New York, New York, NYView Profile , Richard Pollack Courant Institute of Mathematical Sciences, New York University, New York, NY Courant Institute of Mathematical Sciences, New York University, New York, NYView Profile , Rephael Wenger The Ohio State University, Columbus, OH The Ohio State University, Columbus, OHView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 57–63https://doi.org/10.1145/336154.336178Online:01 May 2000Publication History 0citation233DownloadsMetricsTotal Citations0Total Downloads233Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Let S be a set of n points in R d . The "roundness" of S can be measured by computing the width ! = ! (S) of the thinnest spherical shell (or annulus in R 2 ) that contains S. This paper contains three main results related to computing ! : (i) For d = 2, we can compute in O(n log n) time an annulus containing S whose width is at most 2! (S). We extend this algorithm, so that for any given parameter " ? 0, an annulus containing S whose width is at most (1 + ")! , is computed in time O(n log n + n=" 2 ). (ii) For d 3, given a parameter " ? 0, we can compute a shell containing S of width at most (1+ ")! either in time O \\Gamma n " d log( \\Delta ! " ) \\Delta or in time O \\Gamma n " d\\Gamma2 \\Gamma log n + 1 " \\Delta log \\Gamma \\Delta ! " \\Delta\\Delta . Work by P.A. was supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by NSF grants EIA--9870724, and CCR--9732787, by an NYI award, and by a grant from ...

Consider an arrangement of n hyperplanes in R d . Families of convex polytopes whose boundaries are contained in the union of the hyperplanes are the subject of this paper. We aim to bound their combinatorial complexity. Exact asymptotic bounds were known for the case where the polytopes are cells of the arrangement. Situations where the polytopes are pairwise openly disjoint have also been considered in the past. However, no non-trivial bound was known for the general case where the polytopes may have overlapping interiors, for d > 2. We analyze families of polytopes that do not share vertices. In R 3 we show an O(k 1=3 n 2 ) bound on the number of faces of k such polytopes. We also discuss worst-case lower bounds and higher-dimensional versions of the problem. Among other results, we show that the maximum number of facets of k pairwise vertex-disjoint polytopes in R d is k 1=2 n d=2 ) which is a factor of p n away from the best known upper bound in the range n d 2 ...

Let P be a set of n. points in IRd in general position, i.e., no i + 1 points on a common (i -1)-flat, 1 < i 5 d.A k-set @'P is a set S of E points in P that can be separated from P \ S by a hyperplane.A j-facet of P is an oriented (d -l)simplex spanned by d points in P which has exactly j points from P on the positive side of its affine hull.If P is a planar point set and n is even, a halving edge is an undirected edge between two points, such that the connecting line has the same number of points on either side.The number of (n/2)-sets is twice the number of halving edges.Inspired by Dey's recent proof of a new bound on the number of k-sets we show that where degp is the number of halving edges incident to point p and C is the number of crossing pairs of halving edges.The identity allows us, among other things, to determine the masimum number of halving edges in a set of 12 points.An anaIogous identity holds for j-facets.For P in IR3 we show that for j 5 n/4 -2 the number of cs j)-facets (i.e., i-facets with 0 5 i 5 j) is maximized for sets in convex position, where this number is known to be (j + l)(j + 2)n -2(j + l)(j + 2)(j + 3)/3.For 1; 5 n/4 -1, k2n -k(k -1)(2A + 5)/3 is the tight upper bound for the number of (5 A)-sets (i.e., i-sets with 1 ': i 5 k).'h't of this work %S Performed while R.S. and E.W. were visiting the DlhfAa center in November 1989.while R.S. visited FU Berlin in 1992, while E.W. visited

We study the motion-planning problem for pairs and triples of robots operating in a shared workspace containing n obstacles. A standard way to solve such problems is to view the collection of robots as one composite robot, whose number of degrees of freedom is d, the sum of the numbers of degrees of freedom of the individual robots. We show that it is sufficient to consider a constant number of robot systems whose number of degrees of freedom is at most d \\Gamma 1 for pairs of robots, and d \\Gamma 2 for triples. (The result for a pair assumes that the sum of the number of degrees of freedom of the robots constituting the pair reduces by at least one if the robots are required to stay in contact; for triples a similar assumption is made. Moreover, for triples we need to assume that a solution with positive clearance exists.) We use this to obtain an O(n d ) time algorithm to solve the motion-planning problem for a pair of robots; this is one order of magnitude faster than what the st...

We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem.(a) We review sad simplifi some old proofs in new dwguise and give new proofs of the bound O(n~) for the complexity of the k-th level in an arrangement of n lines.(b) We derive an improved version of Lcn%az Lemma in any dimension, and use it to prove a new bound, 0(n2k2/3), on the complexity of the k-th level in an mangement of n planes in lR3, or on the number of k-sets in a set of n points in three dimensions.(c) We show that the complexity of any single level in an arrangement of n line segments in the plane is O(n312 ), and that the complexity of any single level in an arrangement of n triangles in 3-space is O(n17'6 ).

Article Free Access Share on Average-case ray shooting and minimum weight triangulations Authors: Boris Aronov Computer and Information Science, Polytechnic University, Brooklyn, NY Computer and Information Science, Polytechnic University, Brooklyn, NYView Profile , Steven Fortune Bell Laboratories, Murray Hill, New Jersey Bell Laboratories, Murray Hill, New JerseyView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 203–211https://doi.org/10.1145/262839.262972Published:01 August 1997Publication History 6citation248DownloadsMetricsTotal Citations6Total Downloads248Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of k convex polygons in the plane, with a total of n edges. We show: (1) The maximum complexity of the entire common exterior is Θ(nα(k) + k2). 2 (2) The maximum complexity of a single cell of the common exterior is Θ(nα(k)). (3) The complexity of m distinct cells in the common exterior is O(m23k23log13(k2m) + nlogk) and can be Ω(m23k23 + nα(k)) in the worst case.

We introduce the notion of a star unfolding of the surface ${\cal P}$ of a three-dimensional convex polytope with n vertices, and use it to solve several problems related to shortest paths on ${\cal P}$. The first algorithm computes the edge sequences traversed by shortest paths on ${\cal P}$ in time $O(n^6 \beta (n) \log n)$, where $\beta (n)$ is an extremely slowly growing function. A much simpler $O(n^6)$ time algorithm that finds a small superset of all such edge sequences is also sketched. The second algorithm is an $O(n^{8}\log n)$ time procedure for computing the geodesic diameter of ${\cal P}$: the maximum possible separation of two points on ${\cal P}$ with the distance measured along ${\cal P}$. Finally, we describe an algorithm that preprocesses ${\cal P}$ into a data structure that can efficiently answer the queries of the following form: "Given two points, what is the length of the shortest path connecting them?" Given a parameter $1 \le m \le n^2$, it can preprocess ${\cal P}$ in time $O(n^6 m^{1+\delta})$, for any $\delta > 0$, into a data structure of size $O(n^6m^{1+\delta})$, so that a query can be answered in time $O((\sqrt{n}/m^{1/4}) \log n)$. If one query point always lies on an edge of ${\cal P}$, the algorithm can be improved to use $O(n^5 m^{1+\delta})$ preprocessing time and storage and guarantee $O((n/m)^{1/3} \log n)$ query time for any choice of m between 1 and n.

Let ${\cal F}$ be a collection of nd-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of ${\cal F}$ in expected time $O(n^{d+\epsilon})$ for any $\epsilon > 0$. For d = 3, by combining this algorithm with the point-location technique of Preparata and Tamassia, we can compute, in randomized expected time $O(n^{3+\epsilon})$, for any $\epsilon > 0$, a data structure of size $O(n^{3+\epsilon})$ that, for any query point q, can determine in O(log2n) time the function(s) of ${\cal F}$ that attain the lower envelope at q. As a consequence, we obtain improved algorithmic solutions to several problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the "biggest stick" in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in randomized expected time $O(n^{17/11+\epsilon})$, for any $\epsilon > 0$, improving previous solutions that run in time $O(n^{8/5+\epsilon})$. We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require $O(n^{3+\epsilon})$ storage and preprocessing time, for any $\epsilon > 0$, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,...,Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums $P_i=A_i\oplus (-B)$, for i= 1,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log k), and that it can be $\Omega(nk\alpha(k))$ in the worst case, where n is the total complexity of the individual Minkowski sums P1,...,Pk. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log k log n).

We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k3 + kn log k). This bound is almost tight in the worst case, as there exist collections of polyhedra with $\Omega(k^3+kn\alpha(k))$ union complexity. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k3 + kn log k log n) expected time.

Article Stabbing triangulations by lines in 3D Share on Authors: Pankaj K. Agarwal Department of Computer Science, Box 90129, Duke University, Durham, NC Department of Computer Science, Box 90129, Duke University, Durham, NCView Profile , Boris Aronov Computer Science Department, Polytechnic University, Six MetroTech Center, Brooklyn, NY Computer Science Department, Polytechnic University, Six MetroTech Center, Brooklyn, NYView Profile , Subhash Suri Department of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MO Department of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, MOView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 267–276https://doi.org/10.1145/220279.220308Online:01 September 1995Publication History 14citation354DownloadsMetricsTotal Citations14Total Downloads354Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Visibility with reflection Authors: Boris Aronov Computer Science Department, Polytechnic University, Brooklyn, NY Computer Science Department, Polytechnic University, Brooklyn, NYView Profile , Alan R. Davis Div. of Computer Science, Math. and Science, St. Johns University, Jamaica, NY Div. of Computer Science, Math. and Science, St. Johns University, Jamaica, NYView Profile , Tamal K. Dey Dept. of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, Kharagpur 721302, India Dept. of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, Kharagpur 721302, IndiaView Profile , Sudebkumar P. Pal Dept. of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, Kharagpur 721302, India Dept. of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, Kharagpur 721302, IndiaView Profile , D. Chithra Prasad Dept. of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, Kharagpur 721302, India Dept. of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, Kharagpur 721302, IndiaView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 316–325https://doi.org/10.1145/220279.220313Published:01 September 1995Publication History 3citation320DownloadsMetricsTotal Citations3Total Downloads320Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let F be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces of the lower envelope (i.e., pointwise minimum) of F in expected time O(nd+ϵ), for any ϵ>0. For d=3, by combining this algorithm with the point location technique of Preparata and Tamassia, we can compute, in randomized expected time O(n3+ϵ) for any ϵ>0, a data structure of size O(n3+ϵ) that, given any query point q, can determine in O(log2n) time whether q lies above, below or on the envelope. As a consequence, we obtain improved algorithmic solutions to many problems in computational geometry, including (a) computing the width of a point set in 3-space, (b) computing the biggest stick in a simple polygon in the plane, and (c) computing the smallest-width annulus covering a planar point set. The solutions to these problems run in time O(n17/11+ϵ), for any ϵ>0 improving previous solutions that run in time O(n8/5+ϵ). We also present data structures for (i) performing nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane, and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require O(n3+ϵ) storage and preprocessing time, for any ϵ>0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.

Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,…,Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums Pi=Ai⊕(-B), for i=1,…,k. We show that the combinatorial complexity of the free configuration space of B is O(nklog2k), where n is the total complexity of the individual Minkowski sums P1,…,Pk. The bound is almost tight in the worst case. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nklog3k).

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G={G1,G2,...,Gk} is called a clique cover of G if (i) each Gi is a clique or a bipartite clique, and (ii) the union of Gi is G. The size of the clique cover G is defined as Σki=1 ni, where ni is the number of vertices in Gi. Our main result is that there exist visibility graphs of n nonintersecting line segments in the plane whose smallest clique cover has size Ω(n2/log2n. An upper bound of 0(n2/log n) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of size O(n log3 n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n log n).

We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k/sup 3/+knlog/sup 2/ k). This bound is almost tight in the worst case. We also describe a rather simple randomized incremental algorithm for computing the boundary of the union in O(k/sup 3/+knlog/sup 3/ k) expected time.>

We show that the total number of faces bounding any single cell in an arrangement of n (d–1)-simplices in IRd is O(nd–1 log n), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We then extend our analysis technique to derive other results on complexity in simplex arrangements. For example, we show that the number of vertices in such an arrangement, which are incident to the same cell on more than one “side,” is O(nd-1 log n). We also show that the number of repetitons of a “k-flap,” formed by intersecting d–k simplices, along the boundary of the same cell, summed over all cells and all k-flaps, is O(nd-1 log n). We use this quantity, which we call the excess of the arrangement, to derive bounds on the complexity of m distinct cells of such an arrangement.

The power diagram of n weighted sites in d-space partitions a given m-point s e t i n to clusters, one cluster for each region of the diagram.In this way, an assignment o f points to sites is induced.We s h o w the equivalence of such assignments to Euclidean least-squares assignments.As a corollary, there always exists a power diagram whose regions partition a given d-dimensional m-point set into clusters of prescribed sizes, no matter where the sites are taken.Another consequence is that least-squares assignments can be computed by nding suitable weights for the sites.In the plane, this takes roughly O(n 2 m) time and optimal space O(m) which improves on previous methods.We further show that least-squares assignments can be computed by solving a particular linear program in n + 1 dimensions.This leads to a gradient method for iteratively improving the weights.Aside from the obvious application, least-squares assignments are shown to be useful in solving a certain transportation problem and in nding least-squares ttings when translation and scaling are allowed.Finally, w e extend the concept of least-squares assignments to continious point sets, thereby obtaining results on power diagrams with prescribed region volumes that are related to Minkowski's Theorem for convex polytopes.

Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally.We show that any n points in general position possess a crossing family of size at least ~, and describe an O(n log n)-time algorithm for finding one.

Article On the sum of squares of cell complexities in hyperplane arrangements Share on Authors: Boris Aronov Department of Computer Science, Polytechnic University, Brooklyn, NY Department of Computer Science, Polytechnic University, Brooklyn, NYView Profile , Jiří Matoušek Department of Applied Mathematics, Charles University, 118 00 Praha 1, Czechoslovakia Department of Applied Mathematics, Charles University, 118 00 Praha 1, CzechoslovakiaView Profile , Micha Sharir School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel and Courant Institute of Mathematical Sciences, New York University, NY School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel and Courant Institute of Mathematical Sciences, New York University, NYView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 307–313https://doi.org/10.1145/109648.109682Online:01 June 1991Publication History 12citation204DownloadsMetricsTotal Citations12Total Downloads204Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Nonoverlap of the star unfolding Authors: Boris Aronov Computer Science Department, Polytechnic University, Brooklyn, NY Computer Science Department, Polytechnic University, Brooklyn, NYView Profile , Joseph O'Rourke DePartment of Computer Science, Smith college, Northampton, MA DePartment of Computer Science, Smith college, Northampton, MAView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 105–114https://doi.org/10.1145/109648.109660Online:01 June 1991Publication History 2citation269DownloadsMetricsTotal Citations2Total Downloads269Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let P be (the boundary of) a simple polygon with n vertices. For a vertex p of P, let ϕ(p) be the set of points on P that are farthest from p, where the distance between two points is the length of the (Euclidean) shortest path that connects them without intersecting the interior of P. In this paper, we present an O(n log n) algorithm to compute a member of ϕ(p) for every vertex p of P. As a corollary, the external diameter of P can also be computed in the same time.

We describe a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo [Me1]. The expected running time of our algorithm is Ο(n4/3 log 8/3 n). A deterministic version of our procedure runs in time Ο(n3/2 log5/2 n). Both versions improve the previously best known upper bound of Ο(n9/5 log4/5 n) by Chazelle [Ch]. A simple Ο(n log n) time algorithm for computing an approximation of the median distance is also presented.

We prove that for any set S of n points in the plane and n3-α triangles spanned by the points of S there exists a point (not necessarily of S) contained in at least n3-3α/(512 log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most 6.4n8/3 log5/3 n halving planes.

Article Free Access Share on The furthest-site geodesic Voronoi diagram Authors: B. Aronov Courant Institute of Mathematical Sciences, NYU Courant Institute of Mathematical Sciences, NYUView Profile , S. Fortune AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile , G. Wilfong AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims SCG '88: Proceedings of the fourth annual symposium on Computational geometryJanuary 1988 Pages 229–240https://doi.org/10.1145/73393.73417Published:06 January 1988Publication History 2citation531DownloadsMetricsTotal Citations2Total Downloads531Last 12 Months25Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We show that the combinatorial complexity of all non-convex cells in an arrangement of n (possibly intersecting) triangles in 3-space is Ο(n7/3+δ), for any δ>0, and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement, analyze some special cases of the problem where improved bounds (and better algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.

Given a simple polygon with n sides in the plane and a set of k point “sites” in its interior or on the boundary, compute the Voronol diagram of the set of sites using the internal “geodesic” distance inside the polygon as the metric. We describe an Ο((n+k) log2(n+k)) time algorithm for solving this problem and sketch a faster Ο((n+k) log(n+k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.