On the Most Likely Convex Hull of Uncertain Points

Download

index.pdf

Date

2013-01-01

Author

Suri, Subhash
Verbeek, Kevin
Yıldız, Hakan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

58
views

122
downloads

Consider a set of points in d dimensions where the existence or the location of each point is determined by a probability distribution. The convex hull of this set is a random variable distributed over exponentially many choices. We are interested in finding the most likely convex hull, namely, the one with the maximum probability of occurrence. We investigate this problem under two natural models of uncertainty: the point (also called the tuple) model where each point (site) has a fixed position si but only exists with some probability pi(i), for 0 = 3 dimensions. On the other hand, we show that the problem is NP-hard under the multipoint model even for d = 2 dimensions. We also present hardness results for approximating the probability of the most likely hull. While we focus on the most likely hull for concreteness, our results hold for other natural definitions of a probabilistic hull.

URI

https://hdl.handle.net/11511/93922

DOI

https://doi.org/10.1007/978-3-642-40450-4_67

Conference Name

21st Annual European Symposium on Algorithms (ESA)

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

On a Fitting length conjecture without the coprimeness condition Ercan, Gülin (Springer Science and Business Media LLC, 2012-08-01) Let A be a finite nilpotent group acting fixed point freely by automorphisms on the finite solvable group G. It is conjectured that the Fitting length of G is bounded by the number of primes dividing the order of A, counted with multiplicities. The main result of this paper shows that the conjecture is true in the case where A is cyclic of order p (n) q, for prime numbers p and q coprime to 6 and G has abelian Sylow 2-subgroups.
ON THE NUMBER OF QUADRATIC FORMS HAVING CODIMENSION 2 RADICALS IN CHARACTERISTIC 2 GIVING MAXIMAL/MINIMAL CURVES Özbudak, Ferruh (Informa UK Limited, 2014-09-02) Let F-q be an arbitrary finite field of characteristic 2 and k be an arbitrary even integer. We count the number of quadratic forms having codimension 2 radicals on F-q(k) over F-q such that the corresponding curve is maximal or minimal. This problem is first attempted in [3], in which the number of maximal curves is obtained only for (q, k) = (2, 6) and (q, k) = (2, 8).
APPROXIMATION OF EXCESSIVE BACKLOG PROBABILITIES OF TWO TANDEM QUEUES Sezer, Ali Devin (2018-09-01) Let X be the constrained random walk on Z(+)(2) having increments (1, 0), (-1, 1), and (0, -1) with respective probabilities A lambda,mu 1, and mu 2 representing the lengths of two tandem queues. We assume that X is stable and mu 1 not equal mu 2. Let tau(n) be the first time when the sum of the components of X equals n. Let Y be the constrained random walk on Z x Z(+) having increments (-1, 0), (1, 1), and (0, -1) with probabilities lambda, mu(1), and mu(2). Let tau be the first time that the components of...
On the generating graphs of the symmetric and alternating groups Erdem, Fuat; Ercan, Gülin; Maróti, Attila; Department of Mathematics (2018) Dixon showed that the probability that a random pair of elements in the symmetric group $S_n$ generates $S_n$ or the alternating group $A_n$ tends to $1$ as $n to infty$. (A generalization of this result was given by Babai and Hayes.) The generating graph $Gamma(G)$ of a finite group $G$ is defined to be the simple graph on the set of non-identity elements of $G$ with the property that two elements are connected by and edge if and only if they generate $G$. The purpose of this thesis is to study the graphs ...
On the units generated by Weierstrass forms Küçüksakallı, Ömer (2014-01-01) There is an algorithm of Schoof for finding divisors of class numbers of real cyclotomic fields of prime conductor. In this paper we introduce an improvement of the elliptic analogue of this algorithm by using a subgroup of elliptic units given by Weierstrass forms. These elliptic units which can be expressed in terms of x-coordinates of points on elliptic curves enable us to use the fast arithmetic of elliptic curves over finite fields.

Citation Formats

S. Suri, K. Verbeek, and H. Yıldız, “On the Most Likely Convex Hull of Uncertain Points,” Sophia Antipolis, Fransa, 2013, vol. 8125, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/93922.