6 Search Results for "Yap, Chee"


Document
Media Exposition
Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition)

Authors: Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
Given a set P of n points, the sum of distances function of a point x is d_{P}(x) : = ∑_{p ∈ P} ||x - p||. Using a subdivision approach with soft predicates we implement and visualize approximate solutions for three different problems involving the sum of distances function in ℝ². Namely, (1) finding the Fermat-Weber point, (2) constructing n-ellipses of a given set of points, and (3) constructing the nearest Voronoi diagram under the sum of distances function, given a set of point clusters as sites.

Cite as

Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap. Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 69:1-69:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{mantas_et_al:LIPIcs.SoCG.2022.69,
  author =	{Mantas, Ioannis and Papadopoulou, Evanthia and Suderland, Martin and Yap, Chee},
  title =	{{Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{69:1--69:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.69},
  URN =		{urn:nbn:de:0030-drops-160773},
  doi =		{10.4230/LIPIcs.SoCG.2022.69},
  annote =	{Keywords: Fermat point, geometric median, Weber point, Fermat distance, sum of distances, n-ellipse, multifocal ellipse, min-sum Voronoi diagram, cluster Voronoi diagram}
}
Document
Certified Approximation Algorithms for the Fermat Point and n-Ellipses

Authors: Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
Given a set A of n points in ℝ^d with weight function w: A→ℝ_{> 0}, the Fermat distance function is φ(x): = ∑_{a∈A}w(a)‖x-a‖. A classic problem in facility location dating back to 1643, is to find the Fermat point x*, the point that minimizes the function φ. We consider the problem of computing a point x̃* that is an ε-approximation of x* in the sense that ‖x̃*-x*‖<ε. The algorithmic literature has so far used a different notion based on ε-approximation of the value φ(x*). We devise a certified subdivision algorithm for computing x̃*, enhanced by Newton operator techniques. We also revisit the classic Weiszfeld-Kuhn iteration scheme for x*, turning it into an ε-approximate Fermat point algorithm. Our second problem is the certified construction of ε-isotopic approximations of n-ellipses. These are the level sets φ^{-1}(r) for r > φ(x*) and d = 2. Finally, all our planar (d = 2) algorithms are implemented in order to experimentally evaluate them, using both synthetic as well as real world datasets. These experiments show the practicality of our techniques.

Cite as

Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap. Certified Approximation Algorithms for the Fermat Point and n-Ellipses. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{junginger_et_al:LIPIcs.ESA.2021.54,
  author =	{Junginger, Kolja and Mantas, Ioannis and Papadopoulou, Evanthia and Suderland, Martin and Yap, Chee},
  title =	{{Certified Approximation Algorithms for the Fermat Point and n-Ellipses}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{54:1--54:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.54},
  URN =		{urn:nbn:de:0030-drops-146359},
  doi =		{10.4230/LIPIcs.ESA.2021.54},
  annote =	{Keywords: Fermat point, n-ellipse, subdivision, approximation, certified, algorithms}
}
Document
Fréchet Mean and p-Mean on the Unit Circle: Decidability, Algorithm, and Applications to Clustering on the Flat Torus

Authors: Frédéric Cazals, Bernard Delmas, and Timothee O'Donnell

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)


Abstract
The center of mass of a point set lying on a manifold generalizes the celebrated Euclidean centroid, and is ubiquitous in statistical analysis in non Euclidean spaces. In this work, we give a complete characterization of the weighted p-mean of a finite set of angular values on S¹, based on a decomposition of S¹ such that the functional of interest has at most one local minimum per cell. This characterization is used to show that the problem is decidable for rational angular values -a consequence of Lindemann’s theorem on the transcendence of π, and to develop an effective algorithm parameterized by exact predicates. A robust implementation of this algorithm based on multi-precision interval arithmetic is also presented, and is shown to be effective for large values of n and p. We use it as building block to implement the k-means and k-means++ clustering algorithms on the flat torus, with applications to clustering protein molecular conformations. These algorithms are available in the Structural Bioinformatics Library (http://sbl.inria.fr). Our derivations are of interest in two respects. First, efficient p-mean calculations are relevant to develop principal components analysis on the flat torus encoding angular spaces-a particularly important case to describe molecular conformations. Second, our two-stage strategy stresses the interest of combinatorial methods for p-means, also emphasizing the role of numerical issues.

Cite as

Frédéric Cazals, Bernard Delmas, and Timothee O'Donnell. Fréchet Mean and p-Mean on the Unit Circle: Decidability, Algorithm, and Applications to Clustering on the Flat Torus. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{cazals_et_al:LIPIcs.SEA.2021.15,
  author =	{Cazals, Fr\'{e}d\'{e}ric and Delmas, Bernard and O'Donnell, Timothee},
  title =	{{Fr\'{e}chet Mean and p-Mean on the Unit Circle: Decidability, Algorithm, and Applications to Clustering on the Flat Torus}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.15},
  URN =		{urn:nbn:de:0030-drops-137870},
  doi =		{10.4230/LIPIcs.SEA.2021.15},
  annote =	{Keywords: Frech\'{e}t mean, p-mean, circular statistics, decidability, robustness, multi-precision, angular spaces, flat torus, clustering, molecular conformations}
}
Document
Rods and Rings: Soft Subdivision Planner for R^3 x S^2

Authors: Ching-Hsiang Hsu, Yi-Jen Chiang, and Chee Yap

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)


Abstract
We consider path planning for a rigid spatial robot moving amidst polyhedral obstacles. Our robot is either a rod or a ring. Being axially-symmetric, their configuration space is R^3 x S^2 with 5 degrees of freedom (DOF). Correct, complete and practical path planning for such robots is a long standing challenge in robotics. While the rod is one of the most widely studied spatial robots in path planning, the ring seems to be new, and a rare example of a non-simply-connected robot. This work provides rigorous and complete algorithms for these robots with theoretical guarantees. We implemented the algorithms in our open-source Core Library. Experiments show that they are practical, achieving near real-time performance. We compared our planner to state-of-the-art sampling planners in OMPL [Sucan et al., 2012]. Our subdivision path planner is based on the twin foundations of epsilon-exactness and soft predicates. Correct implementation is relatively easy. The technical innovations include subdivision atlases for S^2, introduction of Sigma_2 representations for footprints, and extensions of our feature-based technique for "opening up the blackbox of collision detection".

Cite as

Ching-Hsiang Hsu, Yi-Jen Chiang, and Chee Yap. Rods and Rings: Soft Subdivision Planner for R^3 x S^2. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.SoCG.2019.43,
  author =	{Hsu, Ching-Hsiang and Chiang, Yi-Jen and Yap, Chee},
  title =	{{Rods and Rings: Soft Subdivision Planner for R^3 x S^2}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.43},
  URN =		{urn:nbn:de:0030-drops-104477},
  doi =		{10.4230/LIPIcs.SoCG.2019.43},
  annote =	{Keywords: Algorithmic Motion Planning, Subdivision Methods, Resolution-Exact Algorithms, Soft Predicates, Spatial Rod Robots, Spatial Ring Robots}
}
Document
Soft Subdivision Motion Planning for Complex Planar Robots

Authors: Bo Zhou, Yi-Jen Chiang, and Chee Yap

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


Abstract
The design and implementation of theoretically-sound robot motion planning algorithms is challenging. Within the framework of resolution-exact algorithms, it is possible to exploit soft predicates for collision detection. The design of soft predicates is a balancing act between easily implementable predicates and their accuracy/effectivity. In this paper, we focus on the class of planar polygonal rigid robots with arbitrarily complex geometry. We exploit the remarkable decomposability property of soft collision-detection predicates of such robots. We introduce a general technique to produce such a decomposition. If the robot is an m-gon, the complexity of this approach scales linearly in m. This contrasts with the O(m^3) complexity known for exact planners. It follows that we can now routinely produce soft predicates for any rigid polygonal robot. This results in resolution-exact planners for such robots within the general Soft Subdivision Search (SSS) framework. This is a significant advancement in the theory of sound and complete planners for planar robots. We implemented such decomposed predicates in our open-source Core Library. The experiments show that our algorithms are effective, perform in real time on non-trivial environments, and can outperform many sampling-based methods.

Cite as

Bo Zhou, Yi-Jen Chiang, and Chee Yap. Soft Subdivision Motion Planning for Complex Planar Robots. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.ESA.2018.73,
  author =	{Zhou, Bo and Chiang, Yi-Jen and Yap, Chee},
  title =	{{Soft Subdivision Motion Planning for Complex Planar Robots}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.73},
  URN =		{urn:nbn:de:0030-drops-95361},
  doi =		{10.4230/LIPIcs.ESA.2018.73},
  annote =	{Keywords: Computational Geometry, Algorithmic Motion Planning, Resolution-Exact Algorithms, Soft Predicates, Planar Robots with Complex Geometry}
}
Document
Path Planning for Simple Robots using Soft Subdivision Search

Authors: Ching-Hsiang Hsu, John Paul Ryan, and Chee Yap

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)


Abstract
The concept of resolution-exact path planning is a theoretically sound alternative to the standard exact algorithms, and provides much stronger guarantees than probabilistic or sampling algorithms. It opens the way for the introduction of soft predicates in the context of subdivision algorithm. Taking a leaf from the great success of the Probabilistic Road Map (PRM) framework, we formulate an analogous framework for subdivision, called Soft Subdivision Search (SSS). In this video, we illustrate the SSS framework for a trio of simple planar robots: disc, triangle and 2-links. These robots have, respectively, 2, 3 and 4 degrees of freedom. Our 2-link robot can also avoid self-crossing. These algorithms operate in realtime and are relatively easy to implement.

Cite as

Ching-Hsiang Hsu, John Paul Ryan, and Chee Yap. Path Planning for Simple Robots using Soft Subdivision Search. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 68:1-68:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.SoCG.2016.68,
  author =	{Hsu, Ching-Hsiang and Ryan, John Paul and Yap, Chee},
  title =	{{Path Planning for Simple Robots using Soft Subdivision Search}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{68:1--68:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.68},
  URN =		{urn:nbn:de:0030-drops-59607},
  doi =		{10.4230/LIPIcs.SoCG.2016.68},
  annote =	{Keywords: Robot Path Planning, Soft Predicates, Resolution-Exact Algorithm, Subdivision Search}
}
  • Refine by Author
  • 5 Yap, Chee
  • 2 Chiang, Yi-Jen
  • 2 Hsu, Ching-Hsiang
  • 2 Mantas, Ioannis
  • 2 Papadopoulou, Evanthia
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 2 Computing methodologies → Robotic planning
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 3 Soft Predicates
  • 2 Algorithmic Motion Planning
  • 2 Fermat point
  • 2 Resolution-Exact Algorithms
  • 2 n-ellipse
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2021
  • 1 2016
  • 1 2018
  • 1 2019
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail