12 Search Results for "Abdelkader, Ahmed"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.3
Circle-Segment Intersection Queries in Connected Geometric Graphs

Authors: Peyman Afshani, Yannick Bosch, and Sabine Storandt

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In this paper, we study the problem of efficiently reporting all intersections between a given set of line segments in the plane and a query circle, focusing on the case where the segments form the edges of a connected geometric graph. While previous data structures for circle-segment intersection queries on general segment sets incur high space or query time costs, we exploit the connectivity of the input to obtain significantly improved performance. In fact, we propose a new circle-segment intersection data structure that can be constructed in 𝒪((n + C) log³ n) time and space on connected graphs with n edges and C edge crossings. It answers intersection queries in 𝒪(k log³ n) time, where k denotes the output size. Our method relies on the construction of efficient circle-graph intersection oracles as well as a novel linear-time algorithm to partition the edges of the graph into balanced, connected components, which might be of independent interest. In a proof-of-concept experimental study on real-world road networks, we show that our novel data structure also performs well in practice. Even on networks with millions of edges, the construction time is within minutes and queries are answered in a few milliseconds.
Cite as

Peyman Afshani, Yannick Bosch, and Sabine Storandt. Circle-Segment Intersection Queries in Connected Geometric Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ISAAC.2025.3,
  author =	{Afshani, Peyman and Bosch, Yannick and Storandt, Sabine},
  title =	{{Circle-Segment Intersection Queries in Connected Geometric Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.3},
  URN =		{urn:nbn:de:0030-drops-249114},
  doi =		{10.4230/LIPIcs.ISAAC.2025.3},
  annote =	{Keywords: Intersection data structure, Graph partitioning, Dobkin-Kirkpatrick hierarchy}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.45
Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences

Authors: Tuyen Pham and Hubert Wagner

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
The contributions of the paper span theoretical and implementational results. First, we prove that Kd-trees can be extended to ℝ^d with the distance measured by an arbitrary Bregman divergence. Perhaps surprisingly, this shows that the triangle inequality is not necessary for correct pruning in Kd-trees. Second, we offer an efficient algorithm and C++ implementation for nearest neighbour search for decomposable Bregman divergences. The implementation supports the Kullback-Leibler divergence (relative entropy) which is a popular distance between probability vectors and is commonly used in statistics and machine learning. This is a step toward broadening the usage of computational geometry algorithms. Our benchmarks show that our implementation efficiently handles both exact and approximate nearest neighbour queries. Compared to a linear search, we achieve two orders of magnitude speedup for practical scenarios in dimension up to 100. Our solution is simpler and more efficient than competing methods.
Cite as

Tuyen Pham and Hubert Wagner. Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pham_et_al:LIPIcs.WADS.2025.45,
  author =	{Pham, Tuyen and Wagner, Hubert},
  title =	{{Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.45},
  URN =		{urn:nbn:de:0030-drops-242766},
  doi =		{10.4230/LIPIcs.WADS.2025.45},
  annote =	{Keywords: Kd-tree, k-d tree, nearest neighbour search, Bregman divergence, decomposable Bregman divergence, KL divergence, relative entropy, cross entropy, Shannon’s entropy}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.48
Farthest-Point Voronoi Diagrams in the Hilbert Metric

Authors: Minju Song, Mook Kwon Jung, and Hee-Kap Ahn

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
The Hilbert metric, introduced by David Hilbert in 1895, is a projective metric defined on a bounded convex domain in a Euclidean space. For a convex polygon with m vertices and n point sites lying inside the polygon in the plane, it is shown that the nearest-point Voronoi diagram in the Hilbert metric has combinatorial complexity of O(mn) [Gezalyan and Mount, SoCG 2023]. In this paper, we show that the farthest-point Voronoi diagram in the Hilbert metric has combinatorial complexity O(m), which is independent of the number of sites. Also, we present an efficient algorithm to compute the farthest-point Voronoi diagram.
Cite as

Minju Song, Mook Kwon Jung, and Hee-Kap Ahn. Farthest-Point Voronoi Diagrams in the Hilbert Metric. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{song_et_al:LIPIcs.WADS.2025.48,
  author =	{Song, Minju and Jung, Mook Kwon and Ahn, Hee-Kap},
  title =	{{Farthest-Point Voronoi Diagrams in the Hilbert Metric}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.48},
  URN =		{urn:nbn:de:0030-drops-242797},
  doi =		{10.4230/LIPIcs.WADS.2025.48},
  annote =	{Keywords: Farthest-point Voronoi diagram, Hilbert metric, Complexity, Algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.74
Drainability and Fillability of Polyominoes in Diverse Models of Global Control

Authors: Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Tilt models offer intuitive and clean definitions of complex systems in which particles are influenced by global control commands. Despite a wide range of applications, there has been almost no theoretical investigation into the associated issues of filling and draining geometric environments. This is partly because a globally controlled system (i.e., passive matter) exhibits highly complex behavior that cannot be locally restricted. Thus, there is a strong need for theoretical studies that investigate these models both (1) in terms of relative power to each other, and (2) from a complexity theory perspective. In this work, we provide (1) general tools for comparing and contrasting different models of global control, and (2) both complexity and algorithmic results on filling and draining.
Cite as

Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer. Drainability and Fillability of Polyominoes in Diverse Models of Global Control. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 74:1-74:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ICALP.2025.74,
  author =	{Fekete, S\'{a}ndor P. and Kramer, Peter and Reinhardt, Jan-Marc and Rieck, Christian and Scheffer, Christian},
  title =	{{Drainability and Fillability of Polyominoes in Diverse Models of Global Control}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{74:1--74:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.74},
  URN =		{urn:nbn:de:0030-drops-234518},
  doi =		{10.4230/LIPIcs.ICALP.2025.74},
  annote =	{Keywords: Global control, full Tilt, single Tilt, Fillability, Drainability, Polyominoes, Complexity}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.82
Software for the Thompson and Funk Polygonal Geometry (Media Exposition)

Authors: Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, and David M. Mount

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Metric spaces defined within convex polygons, such as the Thompson, Funk, reverse Funk, and Hilbert metrics, are subjects of recent exploration and study in computational geometry. This paper contributes an educational piece of software for understanding these unique geometries while also providing a tool to support their research. We provide dynamic software for manipulating the Funk, reverse Funk, and Thompson balls in convex polygonal domains. Additionally, we provide a visualization program for traversing the Hilbert polygonal geometry.
Cite as

Hridhaan Banerjee, Carmen Isabel Day, Auguste H. Gezalyan, Olga Golovatskaia, Megan Hunleth, Sarah Hwang, Nithin Parepally, Lucy Wang, and David M. Mount. Software for the Thompson and Funk Polygonal Geometry (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 82:1-82:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:LIPIcs.SoCG.2025.82,
  author =	{Banerjee, Hridhaan and Day, Carmen Isabel and Gezalyan, Auguste H. and Golovatskaia, Olga and Hunleth, Megan and Hwang, Sarah and Parepally, Nithin and Wang, Lucy and Mount, David M.},
  title =	{{Software for the Thompson and Funk Polygonal Geometry}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{82:1--82:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.82},
  URN =		{urn:nbn:de:0030-drops-232349},
  doi =		{10.4230/LIPIcs.SoCG.2025.82},
  annote =	{Keywords: Thompson metric, Hilbert metric, Funk metric, balls}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.5
Smooth Distance Approximation

Authors: Ahmed Abdelkader and David M. Mount

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Traditional problems in computational geometry involve aspects that are both discrete and continuous. One such example is nearest-neighbor searching, where the input is discrete, but the result depends on distances, which vary continuously. In many real-world applications of geometric data structures, it is assumed that query results are continuous, free of jump discontinuities. This is at odds with many modern data structures in computational geometry, which employ approximations to achieve efficiency, but these approximations often suffer from discontinuities. In this paper, we present a general method for transforming an approximate but discontinuous data structure into one that produces a smooth approximation, while matching the asymptotic space efficiencies of the original. We achieve this by adapting an approach called the partition-of-unity method, which smoothly blends multiple local approximations into a single smooth global approximation. We illustrate the use of this technique in a specific application of approximating the distance to the boundary of a convex polytope in ℝ^d from any point in its interior. We begin by developing a novel data structure that efficiently computes an absolute ε-approximation to this query in time O(log (1/ε)) using O(1/ε^{d/2}) storage space. Then, we proceed to apply the proposed partition-of-unity blending to guarantee the smoothness of the approximate distance field, establishing optimal asymptotic bounds on the norms of its gradient and Hessian.
Cite as

Ahmed Abdelkader and David M. Mount. Smooth Distance Approximation. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdelkader_et_al:LIPIcs.ESA.2023.5,
  author =	{Abdelkader, Ahmed and Mount, David M.},
  title =	{{Smooth Distance Approximation}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.5},
  URN =		{urn:nbn:de:0030-drops-186589},
  doi =		{10.4230/LIPIcs.ESA.2023.5},
  annote =	{Keywords: Approximation algorithms, convexity, continuity, partition of unity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.4
Approximate Nearest-Neighbor Search for Line Segments

Authors: Ahmed Abdelkader and David M. Mount

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Approximate nearest-neighbor search is a fundamental algorithmic problem that continues to inspire study due its essential role in numerous contexts. In contrast to most prior work, which has focused on point sets, we consider nearest-neighbor queries against a set of line segments in ℝ^d, for constant dimension d. Given a set S of n disjoint line segments in ℝ^d and an error parameter ε > 0, the objective is to build a data structure such that for any query point q, it is possible to return a line segment whose Euclidean distance from q is at most (1+ε) times the distance from q to its nearest line segment. We present a data structure for this problem with storage O((n²/ε^d) log (Δ/ε)) and query time O(log (max(n,Δ)/ε)), where Δ is the spread of the set of segments S. Our approach is based on a covering of space by anisotropic elements, which align themselves according to the orientations of nearby segments.
Cite as

Ahmed Abdelkader and David M. Mount. Approximate Nearest-Neighbor Search for Line Segments. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abdelkader_et_al:LIPIcs.SoCG.2021.4,
  author =	{Abdelkader, Ahmed and Mount, David M.},
  title =	{{Approximate Nearest-Neighbor Search for Line Segments}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.4},
  URN =		{urn:nbn:de:0030-drops-138039},
  doi =		{10.4230/LIPIcs.SoCG.2021.4},
  annote =	{Keywords: Approximate nearest-neighbor searching, Approximate Voronoi diagrams, Line segments, Macbeath regions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.47
Coresets for the Nearest-Neighbor Rule

Authors: Alejandro Flores-Velazco and David M. Mount

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Given a training set P of labeled points, the nearest-neighbor rule predicts the class of an unlabeled query point as the label of its closest point in the set. To improve the time and space complexity of classification, a natural question is how to reduce the training set without significantly affecting the accuracy of the nearest-neighbor rule. Nearest-neighbor condensation deals with finding a subset R ⊆ P such that for every point p ∈ P, p’s nearest-neighbor in R has the same label as p. This relates to the concept of coresets, which can be broadly defined as subsets of the set, such that an exact result on the coreset corresponds to an approximate result on the original set. However, the guarantees of a coreset hold for any query point, and not only for the points of the training set. This paper introduces the concept of coresets for nearest-neighbor classification. We extend existing criteria used for condensation, and prove sufficient conditions to correctly classify any query point when using these subsets. Additionally, we prove that finding such subsets of minimum cardinality is NP-hard, and propose quadratic-time approximation algorithms with provable upper-bounds on the size of their selected subsets. Moreover, we show how to improve one of these algorithms to have subquadratic runtime, being the first of this kind for condensation.
Cite as

Alejandro Flores-Velazco and David M. Mount. Coresets for the Nearest-Neighbor Rule. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 47:1-47:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{floresvelazco_et_al:LIPIcs.ESA.2020.47,
  author =	{Flores-Velazco, Alejandro and Mount, David M.},
  title =	{{Coresets for the Nearest-Neighbor Rule}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{47:1--47:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.47},
  URN =		{urn:nbn:de:0030-drops-129138},
  doi =		{10.4230/LIPIcs.ESA.2020.47},
  annote =	{Keywords: coresets, nearest-neighbor rule, classification, nearest-neighbor condensation, training-set reduction, approximate nearest-neighbor, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.1
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm

Authors: Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, and Ahmad A. Rushdi

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We study the problem of decomposing a volume bounded by a smooth surface into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled solution to this problem for generic smooth surfaces remained elusive. VoroCrust leverages ideas from alpha-shapes and the power crust algorithm to produce unweighted Voronoi cells conforming to the surface, yielding the first provably-correct algorithm for this problem. Given an epsilon-sample on the bounding surface, with a weak sigma-sparsity condition, we work with the balls of radius delta times the local feature size centered at each sample. The corners of this union of balls are the Voronoi sites, on both sides of the surface. The facets common to cells on opposite sides reconstruct the surface. For appropriate values of epsilon, sigma and delta, we prove that the surface reconstruction is isotopic to the bounding surface. With the surface protected, the enclosed volume can be further decomposed into an isotopic volume mesh of fat Voronoi cells by generating a bounded number of sites in its interior. Compared to state-of-the-art methods based on clipping, VoroCrust cells are full Voronoi cells, with convexity and fatness guarantees. Compared to the power crust algorithm, VoroCrust cells are not filtered, are unweighted, and offer greater flexibility in meshing the enclosed volume by either structured grids or random samples.
Cite as

Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, and Ahmad A. Rushdi. Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abdelkader_et_al:LIPIcs.SoCG.2018.1,
  author =	{Abdelkader, Ahmed and Bajaj, Chandrajit L. and Ebeida, Mohamed S. and Mahmoud, Ahmed H. and Mitchell, Scott A. and Owens, John D. and Rushdi, Ahmad A.},
  title =	{{Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.1},
  URN =		{urn:nbn:de:0030-drops-87147},
  doi =		{10.4230/LIPIcs.SoCG.2018.1},
  annote =	{Keywords: sampling conditions, surface reconstruction, polyhedral meshing, Voronoi}
}
Document
Multimedia Exposition
DOI: 10.4230/LIPIcs.SoCG.2018.77
VoroCrust Illustrated: Theory and Challenges (Multimedia Exposition)

Authors: Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, and Ahmad A. Rushdi

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Over the past decade, polyhedral meshing has been gaining popularity as a better alternative to tetrahedral meshing in certain applications. Within the class of polyhedral elements, Voronoi cells are particularly attractive thanks to their special geometric structure. What has been missing so far is a Voronoi mesher that is sufficiently robust to run automatically on complex models. In this video, we illustrate the main ideas behind the VoroCrust algorithm, highlighting both the theoretical guarantees and the practical challenges imposed by realistic inputs.
Cite as

Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, and Ahmad A. Rushdi. VoroCrust Illustrated: Theory and Challenges (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 77:1-77:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abdelkader_et_al:LIPIcs.SoCG.2018.77,
  author =	{Abdelkader, Ahmed and Bajaj, Chandrajit L. and Ebeida, Mohamed S. and Mahmoud, Ahmed H. and Mitchell, Scott A. and Owens, John D. and Rushdi, Ahmad A.},
  title =	{{VoroCrust Illustrated: Theory and Challenges}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{77:1--77:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.77},
  URN =		{urn:nbn:de:0030-drops-87903},
  doi =		{10.4230/LIPIcs.SoCG.2018.77},
  annote =	{Keywords: sampling, surface reconstruction, polyhedral meshing, Voronoi}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.4
Economical Delone Sets for Approximating Convex Bodies

Authors: Ahmed Abdelkader and David M. Mount

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
Convex bodies are ubiquitous in computational geometry and optimization theory. The high combinatorial complexity of multidimensional convex polytopes has motivated the development of algorithms and data structures for approximate representations. This paper demonstrates an intriguing connection between convex approximation and the classical concept of Delone sets from the theory of metric spaces. It shows that with the help of a classical structure from convexity theory, called a Macbeath region, it is possible to construct an epsilon-approximation of any convex body as the union of O(1/epsilon^{(d-1)/2}) ellipsoids, where the center points of these ellipsoids form a Delone set in the Hilbert metric associated with the convex body. Furthermore, a hierarchy of such approximations yields a data structure that answers epsilon-approximate polytope membership queries in O(log (1/epsilon)) time. This matches the best asymptotic results for this problem, by a data structure that both is simpler and arguably more elegant.
Cite as

Ahmed Abdelkader and David M. Mount. Economical Delone Sets for Approximating Convex Bodies. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abdelkader_et_al:LIPIcs.SWAT.2018.4,
  author =	{Abdelkader, Ahmed and Mount, David M.},
  title =	{{Economical Delone Sets for Approximating Convex Bodies}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.4},
  URN =		{urn:nbn:de:0030-drops-88300},
  doi =		{10.4230/LIPIcs.SWAT.2018.4},
  annote =	{Keywords: Approximate polytope membership, Macbeath regions, Delone sets, Hilbert geometry}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.1
2048 Without New Tiles Is Still Hard

Authors: Ahmed Abdelkader, Aditya Acharya, and Philip Dasler

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
We study the computational complexity of a variant of the popular 2048 game in which no new tiles are generated after each move. As usual, instances are defined on rectangular boards of arbitrary size. We consider the natural decision problems of achieving a given constant tile value, score or number of moves. We also consider approximating the maximum achievable value for these three objectives. We prove all these problems are NP-hard by a reduction from 3SAT. Furthermore, we consider potential extensions of these results to a similar variant of the Threes! game. To this end, we report on a peculiar motion pattern, that is not possible in 2048, which we found much harder to control by similar board designs.
Cite as

Ahmed Abdelkader, Aditya Acharya, and Philip Dasler. 2048 Without New Tiles Is Still Hard. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{abdelkader_et_al:LIPIcs.FUN.2016.1,
  author =	{Abdelkader, Ahmed and Acharya, Aditya and Dasler, Philip},
  title =	{{2048 Without New Tiles Is Still Hard}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.1},
  URN =		{urn:nbn:de:0030-drops-58858},
  doi =		{10.4230/LIPIcs.FUN.2016.1},
  annote =	{Keywords: Complexity of Games, 2048}
}
  • Refine by Type
  • 12 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 1 2023
  • 1 2021
  • 1 2020
  • 3 2018
  • Show More...

  • Refine by Author
  • 6 Abdelkader, Ahmed
  • 5 Mount, David M.
  • 2 Bajaj, Chandrajit L.
  • 2 Ebeida, Mohamed S.
  • 2 Mahmoud, Ahmed H.
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 9 Theory of computation → Computational geometry
  • 1 Information systems → Data structures
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 2 Complexity
  • 2 Hilbert metric
  • 2 Macbeath regions
  • 2 Voronoi
  • 2 polyhedral meshing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact